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?
twonek napisał(a):
Nadal nie widzę problemu.
Ntrzymaj jakounsigned long long, a pętla wykonuje się10^9razy, 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.
C++ 
#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.
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