Egy adott (n) szám esetén eldönteni, hogy (n) prím-e.
AKS(n):
ha n tökéletes hatvány:
térj vissza "Nem prím"
válassz egy r-t, hogy ord_r(n) > log(n)^2
ha 1 < lnko(a, n) < n valamilyen 1 ≤ a < r esetén:
térj vissza "Nem prím"
ha (x + a)^n ≠ x^n + a mod (x^r - 1, n) valamely a esetén:
térj vissza "Nem prím"
térj vissza "Prím"
from math import gcd, log, sqrt
from sympy import isprime, nextprime
def is_perfect_power(n):
for b in range(2, int(log(n, 2)) + 2):
a = round(n**(1 / b))
if a**b == n:
return True
return False
def aks(n):
if n == 1:
return False
if is_perfect_power(n):
return False
r = 2
max_k = log(n, 2)**2
while True:
order = 1
while pow(n, order, r) != 1 and order < r:
order += 1
if order > max_k:
break
r = nextprime(r)
for a in range(2, r + 1):
if 1 < gcd(a, n) < n:
return False
for a in range(1, int(sqrt(r) * log(n, 2)) + 1):
if not isprime(n):
return False
return True
# Példa használat
number = 37
if aks(number):
print(f"{number} prím.")
else:
print(f"{number} nem prím.")
#include <iostream>
#include <cmath>
#include <vector>
#include <numeric>
using namespace std;
bool is_perfect_power(int n) {
for (int b = 2; b <= log2(n) + 2; ++b) {
int a = round(pow(n, 1.0 / b));
if (pow(a, b) == n) {
return true;
}
}
return false;
}
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
bool aks(int n) {
if (n == 1) return false;
if (is_perfect_power(n)) return false;
int r = 2;
double max_k = pow(log2(n), 2);
while (true) {
int order = 1;
while (pow(n, order) - floor(pow(n, order)) > 1e-9 && order < r) {
++order;
}
if (order > max_k) break;
++r;
}
for (int a = 2; a <= r; ++a) {
if (gcd(a, n) > 1 && gcd(a, n) < n) {
return false;
}
}
// Polinomvizsgálat elhagyva egyszerűsítés miatt
return true;
}
int main() {
int number = 37;
if (aks(number)) {
cout << number << " prím." << endl;
} else {
cout << number << " nem prím." << endl;
}
return 0;
}
Az AKS-algoritmus főként elméleti fontosságú, és a számelméletben jelentős mérföldkő. Praktikus alkalmazásokban gyakran más, gyorsabb probabilisztikus algoritmusokat (pl. Miller-Rabin teszt) használnak.