przekręcanie się long longów

Mam takie zadanie
http://solve.edu.pl/contests/download_desc/2213

i taki kod:
https://wandbox.org/permlink/XozBh83LBn7Hp3oG

Na dwóch testach pokazuje mi błędą odpowiedź. Prawdopodobnie przekręcają się long longi przy mnożeniu w funkcji szybkiego potęgowania.
Pomyślałem o użyciu algorytmu mnożenia rosyjskich chłopów.
To jest prawie taka sama funkcja jak ta którą mam do szybkiego potęgowania, tylko mnożenie trzeba zamienić na dodawanie i...za cholerę mi to nie wychodzi :-(
Ktoś pomoże?

Nie rozumiem, po co mnożenie czy dodawanie. Przecież wystarczy

for (int i = 2; i <= sqrt(n); ++i)
{
    if (n % i == 0)
    {
        cout << "NIE\n";
        return 0;
    }
}
cout << "TAK\n";

1<N <10^18.

Wydaje się że unsigned long long int łapie się na 1<N <10^18.

Nadal nie widzę problemu. N trzymaj jako unsigned long long, a pętla wykonuje się 10^9 razy, więc spokojnie się zmieści w 5s.

twonek napisał(a):

Nadal nie widzę problemu. N trzymaj jako unsigned long long, a pętla wykonuje się 10^9 razy, więc spokojnie się zmieści w 5s.

Przy Twoim pomyślę program działa zbyt długo.

Nie Próbowałeś naiwnym? Mi przy i5 2.6, dla 2^61 - 1 (największa liczba pierwsza Mersenne'a, mieszcząca się w unsigned longu), wychodziło mniej niż pięć sekund.

#include <iostream>

using ull = unsigned long long int;

int naive_prime_test(ull n){
    if (n <= 3) return n > 1;
    else if ( (n % 2 == 0) || (n % 3 == 0) ) return 0;
    ull i = 5;
    while ( i * i <= n){
        if ( (n % i == 0) || ( n % (i + 2) == 0) )
            return 0;
        i += 6;
    }
    return 1;
}


int main() {
	std::cout << naive_prime_test(2305843009213693951L) << "\n";
	return 0;
}

EDIT: Spróbuj może czymś z tego: https://github.com/lion137/Python-Algorithms/blob/master/primarity_tests_one_fermat.py, tylko z pseudokodu do C++ przepisać:)

Można wykorzystać Małe Twierdzenie Fermata, aby z pewnym (dużym o ile wykonamy dużo prób -- np. kilka tysięcy) prawdopodobieństwem stwierdzać czy liczba jest pierwsza.

Weźmy np. liczbę 11.
Z Małe Twierdzenie Fermata wiemy że jeśli policzymy:
2^10 mod 11, to wyjdzie 1
3^10 mod 11, to wyjdzie 1
4^10 mod 11, to wyjdzie 1,
generalnie jak weźmiemy dowolne X względne pierwsze z P, to X^(P-1) mod P, czyli
X^10 mod 11, będzie równe 1

A co jeśli zamiast P=11 weźmiemy np. P=10 (nie jest pierwsze) i spróbujemy liczyć:
X^(P-1) mod p, czyli:
2^9 mod 10
3^9 mod 10
4^9 mod 10
...
to nie mamy gwarancji że zawsze wyjdzie 1, bo p=10 nie jest liczbą pierwszą,
a Małe twierdzenie Fermata nic nie mówi o przypadku gdy P jest złożone
zauważmy że np. 3^9 mod 10 to 3.

W takim razie można to uznać za pewien test pierwszości (dający jakąś szansę na to, że się nie pomylimy):
Aby sprawdzić czy liczba N jest pierwsza, można wiele razy wylosować liczbę X, i jeśli nie jest ona wielokrotnością N (bo tylko wielokrotności liczb pierwszych mogą nie być z nimi względnie pierwsze), liczymy:
X^(N-1) mod N
i jeśli za każdym razem (dla różnych X) wyjdzie 1, to zakładamy, że N jest pierwsze.
Jeśli choć raz wyjdzie reszta z dzielenia różna od 1, to wiemy na pewno, że N jest złożone.

a może https://en.wikipedia.org/wiki/AKS_primality_test ?

Przecież p masz złego typu! Wiec masz limit na wielkość odczytywanych liczb: 2^31 - 1 = 2147483647
Po poprawkach twój kod nadal nie działa https://wandbox.org/permlink/ApBdFxEVfqIcYLkZ

Co do treści zadania należy zwrócić uwagę, że dane wejściowe faktoryzują się do 1 lub 2 liczb pierwszych.
Zapewne trzeba jakoś wykorzystać ten fakt by przyspieszyć algorytm.
Prawdopodobnie chodzi o to: https://pl.wikipedia.org/wiki/Test_Millera-Rabina