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) -- 5.34404 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 = 1000000000000000000000000000171000000000000000000000000009747000000000000000000000000185613 |
i23 : elapsedTime isPrime m3 -- 0.0570663 seconds elapsed o23 = true |
i24 : elapsedTime isPseudoprime m3 -- 0.0001283 seconds elapsed o24 = true |