Det finns en hel del formler för att få fram primtal, men de flesta är ganska besvärliga ur en rent praktisk synpunkt. Det finns algoritmer för primtalstest som är mycket effektivare och snabbare. Wilsons sats t.ex. säger att p >1 är ett primtal om och endast om
(p - 1)! = -mod(p)
Från detta kan följande funktion härledas:
f(n) = 2 + 2*(n!)*mod(n+1)
f(n) genererar primtal för icke-negativa n. Inte särskilt lätt att handskas med när n blir stort dock. Man kan härleda fler formler med Wilsons sats, men de är alla väldigt ineffektiva.
En uppsättning Diofantiska ekvationer i 26 variabler kan användas för att söka primtal. Talet k+2 är ett primtal om och endast om detta ekvationssystem har en lösning i naturliga tal:
0 = wz + h + j − q
0 = (gk + 2g + k + 1)(h + j) + h − z
0 = 16(k + 1)³(k + 2)(n + 1)^2 + 1 − f²
0 = 2n + p + q + z − e
0 = e³(e + 2)(a + 1)² + 1 − o²
0 = (a2 − 1)y² + 1 − x²
0 = 16r²y^4(a² − 1) + 1 − u²
0 = n + l + v − y
0 = (a2 − 1)l² + 1 − m²
0 = ai + k + 1 − l − i
0 = ((a + u²(u² − a))² − 1)(n + 4dy)² + 1 − (x + cu)²
0 = p + l(a − n − 1) + b(2an + 2a − n² − 2n − 2) − m
0 = q + y(a − p − 1) + s(2ap + 2a − p² − 2p − 2) − x
0 = z + pl(a − p) + t(2ap − p² − 1) − pm
Det finns även en uppsättning med 10 variabler sóm genererar primtal.
Mer om dessa ting här:
http://mathworld.wolfram.com/PrimeFormulas.html
http://mathworld.wolfram.com/Prime-G...olynomial.html
