Sito Erastotenesa - która to liczba pierwsza

Question

Zadanie jest takie: 
Dostaję na wejściu liczbę, gdy jest pierwsza mam wyświetlić: 
x jest liczbą pierwszą nr n. I w miejsce n ma być która jest z kolej począwszy od 2. 

Code: 
 

#include <bits/stdc++.h> 
#include <cstdlib>
using namespace std; 
  
void SieveOfEratosthenes(int n, int counting_primes) 
{ 
    bool prime[n+1]; 
    memset(prime, true, sizeof(prime)); 
  
    for (int p=2; p*p<=n; p++) 
    { 
        if (prime[p] == true) 
        { 
            for (int i=p*2; i<=n; i += p) 
	    {
                prime[i] = false; 
	    }
        } 
    } 
  
    for (int p=2; p<=n; p++)
    { 
       if (prime[p]) 
       {
       	  counting_primes ++;
       }
    }
} 


int main() 
{ 
    int n = 0;
    int counting_primes=0;
    cin>>n; 
    SieveOfEratosthenes(n, counting_primes); 
    return 0; 
} 

Problem jest taki, że nie wiem jak napisać sito "raz" i żeby poszczególny test czytał odpowiedzi z tego sita. 

Na razie kod jest dla jednej liczby, ale w zadaniu jest aby wyświetlał się komunikat dla każdej liczby prócz 0 która kończy działanie programu.

Answer 1

Możesz wygenerować tablicę liczb pierwszych do jakiegoś zakresu (o ile jest podany w treści zadania). Następnie możesz używać wyszukiwania binarnego do znalezienia danej liczby.

Comments

zakres jest do 10000000