Python primality checking of 28430288029929701389

Question

I've seen many Python algorithms that check for primality, but I have found that they all fail when checking a particular number: 28430288029929701389

I've used this algorithm: What is the best algorithm for checking if a number is prime?

from __future__ import print_function
import sys
from sys import argv

def is_prime(n):
    if n == 2:
        return True
    if n == 3:
        return True
    if n % 2 == 0:
        return False
    if n % 3 == 0:
        return False

    i = 5
    w = 2

    while i * i <= n:
        if n % i == 0:
            return False

        i += w
        w = 6 - w

    return True

number_to_check = int(argv[1])

if is_prime(number_to_check):
    print("%d is prime" % number_to_check)
else:
    print("%d is not prime" % number_to_check)

and these algorithms: https://coderwall.com/p/utwriw/prime-numbers-with-python#comment_28424

and they all get into an endless loop when checking for primality of this particular number. I can check much bigger numbers and the result comes back instantly. Does anybody know if this is an issue with Python?

For big numbers like this, just run miller-rabin a few times with different bases. For any composite `n`, less than 1/4 of bases are liars for the primality of `n` — Patrick Haugh, Dec 29 '16 at 21:03
https://www.wolframalpha.com/input/?i=Isprime(28430288029929701389) confirms that the number is prime — Dmitry Bychenko, Dec 29 '16 at 21:17
Your assumption "endless loop" is wrong. On my pretty old Mac, I get "28430288029929701389 is prime", taking 18m10.580s of realtime, and only (!) using 1777335335 of the theoretically maximum number of steps 5332006004. — Jongware, Dec 29 '16 at 22:09
As Rad pointed out, it just takes a long time. Sadly the most-upvoted answer to the "what is the best algorithm.." question starts off with a basically incorrect statement (AKS, sigh) and then gives the naive algorithm that's good for tiny inputs but not a good general answer. At least it does point this out later. There are quite a few Python methods that easily handle this number, including packages like gmpy2, sympy, and primefac. — DanaJ, Jan 06 '17 at 06:06

score 6 · Answer 1 · edited Dec 29 '16 at 21:08

Could it be because this number is a prime? Verifying takes sqrt time, and

In [10]: math.sqrt(28430288029929701389)
Out[10]: 5332006004.303606

Python is not a very fast language; looping 5332006004 times can take a long time.

Much larger numbers you're trying can be composite, so a factor is found quickly.

I'd recommend a probabilistic prime testing algorithm like Miller-Rabin or a variation thereof for "real-life" prime testing. These algorithms are drastically faster, and running them multiple times can bring the probability of error to lower than cosmic ray events easily.

score 2 · Accepted Answer · answered Dec 29 '16 at 21:24

Given the __future__ import, I'm guessing you're using Python 2.something?

If so, have you looked into the primefac module? (It doesn't seem to be available for Python 3 yet)

import primefac
biggie = 28430288029929701389
print(list(primefac.primefac(biggie)))
# [28430288029929701389L]
primefac.isprime(biggie)
# True

Per Eli Bendersky's response, this appears to be prime. Also, primefac is returning results for your particular number almost immediately when I run it.

Python primality checking of 28430288029929701389

2 Answers2