Liczby pierwsze - SPOJ zadanie

Question

Zadanie https://pl.spoj.com/problems/PRIME_T/

Wiem ,że w zadaniu trzeba użyć Sita Eratostenesa ,ale nie jestem w stanie wymyślić pełnego warunku do tego sita .Nie wiem jak wyznaczyć liczby mniejsze od pierwiastka[i] ,który równa się (liczba[i]*liczba[i]) .Proszę o nakierowanie mnie co mógłbym wstawić w to miejsce lub też poprawienie mnie jeśli robię coś źle .

if((liczba[i]>1)&&(liczba[i]%(<pierwiastek[i])!=0)) //nie wiem co wstawic w miejsce przed "<pierwiastek"
       {
           cout<<"TAK"<<endl;
       }
       else
        cout<<"NIE"<<endl;

 

Comments

Zła kategoria

Answer 1

Użyj pętli :P Sprawdz wszystkie liczby od 2 do pierwiastka z badanej liczby. Jeśli któraś dzieli się bez reszty to można przerwać pętlę, bo liczba nie jest pierwsza.

Comments

Dzięki ,pomyślę jak to zrobić .

Answer 2

W założeniu zadania masz że każda liczba będzie z przedziału od [1,1000] czyli robisz sito właśnie dla tego przedziału i później elegancko odpowaidasz tak lub nie.

Comments

Dobra ,spróbuję coś zrobić z tym przedziałem ,ale nadal zastanawiam się jak napisać warunek .Dzięki w każdym razie .