Checking for Prime Numbers [closed]

Question

def is_prime(n):
    if n % 2 == 0 and n > 2:
        return False
    return all(n % i for i in xrange(3, int(math.sqrt(n)) + 1, 2))

The code works fine for a range of numbers after that it shows:

OverflowError: Python int too large to convert to C long

How can my code be made faster and more efficient?

Answer 1

On a 64-bit CPython 2.x,

all(i for i in xrange(2**63 - 1))

works, but

all(i for i in xrange(2**63))

overflows. See this explanation, and a workaround. I suggest rewriting this using an old-fashioned while loop.

With Python 3.x,

all(i for i in range(2**63))

works.

---

You've implemented trial division. A more efficient algorithm is the sieve-of-eratosthenes, especially if you want to test multiple numbers for primality. However, the Sieve of Eratosthenes requires more memory, so you'll have to resort to some hacks to make it work for large numbers.

For truly large numbers, you'll have to implement more sophisticated algorithms.