Performs some trial division and then some probabilistic primality tests. If $x$ is definitely composite, the function returns false, otherwise it is declared probably prime, i.e. prime for most practical purposes, and the function returns true. The chance of declaring a composite number prime is very small. Subsequent calls to the same function do not increase the probability of the number being prime. In fact, there are no known numbers which are composite, and for which this function returns true, although it is expected that there are an infinite number of such primes.
This function calls a function in the FLINT library.
i1 : n = 1166513229502037 o1 = 1166513229502037 |
i2 : isPseudoprime n o2 = true |
i3 : isPrime n o3 = true |
i4 : n1 = nextPrime(n+1) o4 = 1166513229502141 |
i5 : factor(n1^2*n)
2
o5 = 1166513229502037*1166513229502141
o5 : Expression of class Product
|
These functions handle numbers larger than this. For example,
i6 : m = 158174196546819165468118574681196546811856748118567481185669501856749 o6 = 158174196546819165468118574681196546811856748118567481185669501856749 |
i7 : isPseudoprime m o7 = true |
i8 : isPrime m o8 = true |
i9 : isPrime m^2 o9 = false |
i10 : factor m^2
2
o10 = 158174196546819165468118574681196546811856748118567481185669501856749
o10 : Expression of class Product
|
i11 : ndigits = 30 o11 = 30 |
i12 : m = nextPrime(10^30) o12 = 1000000000000000000000000000057 |
i13 : m1 = nextPrime (m+10^10) o13 = 1000000000000000000010000000083 |
i14 : m2 = nextPrime (m1 + 10^20) o14 = 1000000000100000000010000000229 |
i15 : isPrime m o15 = true |
i16 : isPrime m1 o16 = true |
i17 : isPrime (m*m1) o17 = false |
i18 : isPrime(m*m*m1*m1*m2^6) o18 = false |
i19 : elapsedTime facs = factor(m*m1) -- 16.7643 seconds elapsed o19 = 1000000000000000000000000000057*1000000000000000000010000000083 o19 : Expression of class Product |
i20 : facs = facs//toList/toList
o20 = {{1000000000000000000000000000057, 1},
-----------------------------------------------------------------------
{1000000000000000000010000000083, 1}}
o20 : List
|
i21 : assert(set facs === set {{m,1}, {m1,1}})
|
i22 : m3 = nextPrime (m^3)
o22 = 10000000000000000000000000001710000000000000000000000000097470000000000
00000000000000185613
|
i23 : elapsedTime isPrime m3 -- 0.116277 seconds elapsed o23 = true |
i24 : elapsedTime isPseudoprime m3 -- 0.000309698 seconds elapsed o24 = true |