Liczby Pierwsze - SPOJ

Question

Witam, mam pytanie, próbuje napisać kod do zadania "Liczby Pierwsze" ze SPOJ-a, ale mój algorytm i kod chyba nie działają tak jak powinien. Treść zadania brzmi następująco:

 

Mój kod wygląda nastepująco: 

#include <iostream>

int main()
{
    int n;
    short a;
    std::cin>>n;
    for(int i=0;i<n;i++)
    {
        std::cin>>a;
        if (a==1)
            std::cout<<"NIE"<<std::endl;
        else if (a==2 || a==3 || a==5 || a==7 || a==11 || a==13 || a==17 || a==19 || a==23 || a==29 || a==31 || a==37 || a==41 || a==43 || a==47 || a==53)
            std::cout<<"TAK"<<std::endl;
        else if ((a%2==0) || (a%3==0) || (a%5==0) || a%7==0 || a%11==0 || a%13==0 || a%17==0 || a%19==0 || a%23==0 || a%29==0 || a%31==0 || a%37==0 || a%41==0 || a%43==0 || a%47==0 || a%53==0)
            std::cout<<"NIE"<<std::endl;
        else if (a%2>0 || a%3>0 || a%5>0 || a%7>0 || a%11>0 || a%13>0 || a%17>0 || a%19>0 || a%23>0 || a%29>0 || a%31>0 || a%37>0 || a%41>0 || a%43>0 || a%47>0 || a%53>0)
            std::cout<<"TAK"<<std::endl;
    }
    return 0;
}

Spoj mi zgłasza błędną odpowiedź, czy powinienem umieścić po prostu więcej warunków, porównań w ifach czy coś pominałem? Wiem, że można napisać to w inny sposób, ale mój pomysł padł na taki i chciałbym go zrealizować do końca, prosiłbym o jakieś rady w tej kwestii.

Answer 1

Jezeli koniecznie chcesz kontynuowac swoj kod to musisz uwzglednic wszystkie liczby pierwsze od 1 do 10000, czyli brakuje ci jakies 1000 liczb do sprawdzenia.... Ale jest też tak ze jezeli liczba nie jest pierwsza to ma dzielnik mniejszy od jej pierwiastka, więc moglbys sprawdzic czy liczba jest podzielna przez jakakolwiek liczbę pierwsza <= pierwiastek z 10 000 to wtedy nie jest pierwsza, inaczej jest

Ale jakby to powiedziec...  w ten sposob sie nic nie nauczysz,  w zadaniu chodzi o napisanie sila erastotenesa i polecam zrobic to z jego pomoca. =]

Comments

Tak też stwierdziłem, myślałem po prostu, że uda mi się zrobić podając tylko max. kilkanaście porównań a potem reszta liczb jakoś się podzieli do tej 10000-tej liczby...

Dzięki za uświadomienie :)

Answer 2

Napisałem coś takiego i w sumie to wydaje mi się że pokazuje poprawnie. Alee no jak wiadomo sądzia wie lepiej.

#include <iostream>
using namespace std;
int x,h,sc=0,j;
string spr(int x)
{
	if(x==1) return "TAK";
	else 
	{
		for(int i=0; i<x; i++){
			j=x-i;
			h=x%j;
			
			if(h==0){
				sc++;
			}
		}
        if(sc==2)
		{
			sc=0;
			return "TAK";
		}
		else
		{
			sc=0;
			return "NIE";
		}
	}
}
int main()
{
	int n;
	cin>>n;
	for(int i=0; i<n; i++)
	{
	cin>>x;
	cout<<spr(x)<<endl;;
	}
	return 0;
}

 

Comments

if(x==1) return "TAK";