wydajność programu

Question

Jak usprawnić ten program, aby działał szybciej? Napisałam go na spoj ale niestety przekracza limit czasu.

#include <iostream>

using namespace std;

bool czy_pierwsza(int number)
{
    if(number<2)
        return false;
    for(int i=2; i<number; ++i){
        if(number%i==0){
            return false;
        }
    }

}

int main()
{
    int n,number;

    cin>>n;

    while(n>=1 && n<=100000){

    for(int i=0; i<n;++i){
        cin>>number;
   if(czy_pierwsza(number)){
       cout<<"TAK"<<endl;
   }else{
       cout<<"NIE"<<endl;
   }
        }
    }
}

 

Answer 1

Żeby sprawdzić czy liczba x jest pierwsza wystarczy sprawdzić czy jest podzielna przez dowolną liczbę od 2 do sqrt(x)

Comments

No to standardowo: nie jestem matematykiem, ale się wypowiem ;-)

Pierwsza sprawa: jeśli liczba nie jest podzielna przez 2, to nie jest również podzielna przez: 4, 6, 8, 10, ... itd.

Analogicznie dla podzielności przez 3, 5, 7, 11 itd.. (Swoją drogą polecam się chwilę zastanowić, jeśli ktoś nie wie, dlaczego wymieniłem akurat takie liczby, pomijając np. liczbę 9. Radzę również poczytać o tzw. sicie Erastotenesa.)

Zastosowanie tej wiedzy skomplikuje algorytm, ale powinno również pozwolić na przyspieszenie obliczeń.

Druga sprawa: to nieco bardziej zaawansowany temat, ale jak ktoś się nie boi algebry modulo, to warto zapoznać się z testem Fermata (oraz innymi tego typu). Nie jest to stuprocentowo pewny test; mówi się nawet o liczbach "prawdopodobnie pierwszych", ale AFAIK w kryptografii jest wykorzystywany. Kto wie, może na SPOJu też się przyda?

Gdyby ktoś zechciał iść tym tropem, to zwrócę tylko uwagę na to, że tam jest mowa o działaniach w algebrze modulo: czyli mamy np. potęgowanie (w modulo). Warto również zaimplementować algorytm szybkiego potęgowania.