4
\$\begingroup\$
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?

\$\endgroup\$
8
  • 3
    \$\begingroup\$ Since the overflow happens only for very large n, I don't consider this to be broken code for the purpose of determining whether this question is on-topic. \$\endgroup\$ Jun 11 '14 at 12:03
  • \$\begingroup\$ @200_success how can i modify this to work for larger number.how to solve my purpose to find whaeter a long int is prime. \$\endgroup\$ Jun 11 '14 at 12:05
  • 1
    \$\begingroup\$ Take a look at this SO question. I can't test this for you because I use Python 3.3, but this may solve your problem. \$\endgroup\$ Jun 11 '14 at 12:17
  • \$\begingroup\$ @DarinDouglass the code works but itertools examples doesn't have minimum range. i want to iterate from 3 \$\endgroup\$ Jun 11 '14 at 12:28
  • \$\begingroup\$ If you look at the Python documentation for itertools.count you'll find it has a start (as well as a step) keyword parameter. \$\endgroup\$ Jun 11 '14 at 12:38
3
\$\begingroup\$

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 , 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.

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.