Wyglada na to, że Chciałes napisać najprostszy test na to czy liczba jest pierwsza; niech będzie java(po pierwsze wystarczy iśc do pierwiastka z n - potem dzielniki sie dublują):
public static boolean prime_test0(long n){
for (long i = 2; i <= Math.sqrt(n); i++)
if (n % i == 0) return false;
return true;
}
To jest dość toporne i wydajnościowo słabe, tzn., ten typ testu zawsze będzie niewydajny, ale można coś tam poprawić, np iść co drugą liczbę (jak sprawdziliśmy dwa, to parzyste odpadają):
public static boolean prime_test1(long n){
if (n % 2 == 0) return false;
for (long i = 3; i <= Math.sqrt(n); i +=2)
if (n % i == 0) return false;
return true;
}
Wiedząc, że wszystkie liczby pierwsze, oprócz 2 i 3 są postaci 6k +- 1, mozemy sprawdzić najpierw je, a potem juz tylko liczby: 6k+1 i 6k-1 <= sqrt(n):
public static boolean prime_test2(long n){
if (n % 2 == 0 || n % 3 == 0) return false;
for (long k = 3; (6 * k - 1) <= Math.sqrt(n) || (6 * k + 1 <= Math.sqrt(n)); k++)
if (n % (6 * k - 1) == 0 || n % (6 * k + 1) == 0) return false;
return true;
}
Ten ostatni można by pewnie zoptymalizowac, ale Masz ideę, a więcej na ten temat jak zwykle tutaj:
https://en.wikipedia.org/wiki/Primality_test