438. Liczby Pierwsze

[demczas]

#include <iostream>

using namespace std;

int n,tmp;
string isPrime(int x);
int main()
{
    cin>>n;
    if(n<100000)
    {
        for(int i=0; i<n; i++)
        {
            cin>>tmp;
            if(tmp>=1&&tmp<=10000)
                cout<<isPrime(tmp)<<endl;
        }
    }
    return 0;
}
string isPrime(int x)
{
    if(x==2||x==3||x==5||x==7)
        return "TAK";
    else if(x>1 && x%2!=0 && x%3!=0 && x%5!=0 && x%7!=0)
        return "TAK";
    else
        return "NIE";
}

Wyskakuje mi, że błędna odpowiedź, ktoś wie dla jakich liczb mój skrypt podaje złą odpowiedź? Wydaję mi się, że powinno być okej..

[sig]

Żeby nie szukać za daleko 121 uznaje za pierwszą, mimo że to 11 * 11. Masz dużo więcej liczb pierwszych do sprawdzenia niż te 4 z twojego kodu

[demczas]

Przepraszam, byłem zbyt leniwy, jak się okazuję ten algorytm sprawdzi się tylko dla małych liczb, poszukałem więcej na ten temat i zastosowałem sito Eratostenesa i SPOJ przyjął rozwiązanie.
Pozdrawiam

[demczas]

Dodam również iż jeśli ktoś chciał by się uprzeć przy zaproponowanej przeze mnie funkcji z kodu wklejonego na początku to należy ją przerobić tak:

-- usunięto działający kod --

Zadziała tylko dla przedziału 1-10000 no i jak widać jest mało elegancka, więc polecam poczytać o sicie Eratostenesa.

[sig]

Nie dajemy tu działających kodów, usuń go.

[piastlis]

Wymyśliłem sito do znajdowania liczb pierwszych.Korzystam z rekurencji i czynników pierwszych.Ponieważ nie znalazłem nic w necie o takim podejściu jestem ciekawy opinii i uwag.Co ciekawe kosztowność czasowa tego algorytmu jest idealnie liniowa a czas wykonywania podobny do sito Atkina .

 #include <iostream>

 using namespace std;
 long long maxlp=0;
  bool S[10000001];
  long long lp[800000]={2};
  long long n;
  long long licznik=0;
 void sito(long long l,long long start)
  {
   for(int i=start;i<=maxlp;i++)
    {
      long long lpom=l*lp[i];
       if(lpom<=n)
        {
          S[lpom]=false;
          sito(lpom,i);
        }
       else
         return;
    }
  }
 int main()
 {
  cin >> n;//Zakres 3-10000000
   for(long long i = 0; i <=n; i++)
    S[i] = true;
  sito(1,0);
  cout <<2<< " ";
   for(long long i = 3; i <=n; i++)
    if(S[i])
     {
       maxlp++;
       lp[maxlp]=i;
       cout <<i<< " ";
       sito(i,0);
     }
     cout <<endl;

 }

[filystyn]

Warto zrobić to zadanie na bardzo dobry czas bo potem będzie potrzebne do zadania działka.

Mi działkę dopiero zaliczyło jak dobiłem w tym zadaniu do 0.01 s. Pozdrawiam.