testing primality

primeprob(n,k: integer):boolean

 

FOR i := 1 TO k DO

. . . a := random(1..n-1)

. . . IF not pseudo(a,n) THEN RETURN F

RETURN T

 

running time : O(k|n|3)

error probability ≤ 4-k

[number of primes ≤ n] ≈ n/ ln n