SPOJ liczby pierwsze C++

pytanie zadane 4 kwietnia 2017 w SPOJ przez Kurogami12 Bywalec (2,610 p.)

Link do ćwiczenia: http://www.spoj.com/problems/PRIME1/ czyli - program ma za zadanie generować liczby pierwsze i faktycznie - działa , tyle że od 1 do 1 000 000 000 zajmuje to no.. sporo więcej czasu niż jest dostępny. Wykorzystałem tutaj sito eratostenesa, jednak nie mam pojęcia jak mógłbym sprawić żeby program działał szybciej. teraz drobny spojler jak ja to zrobiłem (tya..)

int sito(bool *tab, int max)    //tab wskazuje na tablice bool, max to liczba do której ma być sprawdzane
{
    int licznik;         //to jest do pętli while
    for (int i=2; i<sqrt(max); i++)    //tutaj chyba wszystko jest jasne

    {
        if(tab[i-2]==true)    //tutaj żeby pętla faktycznie się wykonywała tylko dla liczb pierwszych
    {
        licznik=i+i;
        while(licznik<max)    //pętla while jest żeby pozbywać się liczb które pierwsze nie są
        {
            tab[licznik-2]=false;        //"wykreśla" liczby pierwsze
            licznik+=i;
        }
            }
        }
}

Byłbym niezmiernie wdzięczny jakby ktoś mnie naprowadził na właściwe tory ewentualnie wytknął błąd.

1 odpowiedź

odpowiedź 29 kwietnia 2017 przez Galit Początkujący (280 p.)

Ja do tego wziąłem się od innej strony pomyślałem że może ifem da się to rozwiązać ale się nie da xD

#include <iostream>

using namespace std;

int n;

int main()
{
    cout << "Podaj liczbe, sprawdzimy czy jest to liczba pierwsza" << endl;
    cin >> n;

if ((n>1)&&(n/1)&&(n/n))
{
    cout <<"TAK";
}
else
{
    cout <<"NIE";
}
    return 0;
}