Zadanie z SPOJ'a o ID 438

Question

Mam problem z zadaniem z SPOJ'a dotyczącym liczb pierwszych. A dokładniej nie wiem jaki powinien być tu warunek lub switch, aby potwierdziło, że ta liczba jest liczbą pierwszą.

int main()
{
    int n, l;
    
    cin >> n;

    for (int i=0; i<n; i++)
    {
        cin >> l;

        if ((l>1) && (l/l==1) && (l/1==l))
            cout << "TAK" << endl;
        else if ((l<=1) && (l%2==0) || (l%3==0) || (l%5==0))
            cout << "NIE" << endl;
    }
    return 0;
}

 

Comments

Proszę o zmianę kategorii na SPOJ, trzymajmy się zasad

Answer 1

Zwykły warunek nie wystarczy... Musisz zastosować pętle.

Pomyśl nad jedną sprawą:

liczba pierwsza to liczba podzielna tylko przez samą siebie i przez jeden, więc idziemy:

1 -> przyjęte jest że jeden nie jest liczbą pierwszą (odpowiadasz NIE)

2 -> dwa to liczba pierwsza (odpowiadasz TAK)

jeżeli większa -> Gdy l nie jest równy ani jeden ani dwa (nie spełnią się te warunki) to zaczynasz algorytm:

masz pętle liczącą od 2 do l-1:

for(int i=2; i <= l-1; i++)

l to oczywiście liczba którą poda użytkownik, dla każdej iteracji obliczasz modulo:

l%i 

Jeżeli wynosi ono jeden to pętla ma się wykonywać nadal (l nie jest podzielne przez i), jeżeli zero to pętle kończysz (widać wyraźnie że to nie jest liczba pierwsza bo da się ją przez coś całkowicie podzielić) i odpowiadasz że nie jest to liczba pierwsza.

Jeżeli pętla się skończy naturalnie to odpowiadasz że to jest liczba pierwsza. To czy pętla skończyła się naturalnie możesz sprawdzić za pomocą jakiejś zmiennej logicznej.

bool x = false; 
(...)
if(l%i==0) {x = true; break;}
(...)
if(x==false) //pętla skończyła się naturalnie (liczba pierwsza)
else //wiadomo 

Są lepsze metody ale ten jest chyba najbardziej prosty