Question about function failing with large number

[Chris Angelico]

On Tue, Aug 13, 2013 at 1:12 PM, Anthony Papillion <papillion at gmail.com> wrote:
> So I'm using the function below to test a large (617 digit) number for
> primality. For some reason, when I execute the code, I get an error
> telling me:
>
> OverflowError: long int too large to convert to float
>
> The error is being thrown on this line:
>
> for x in range(3, int(n**0.5)+1, 2):

Python's integers are unbounded, storing arbitrary precision. Python's
floats are limited to the range of the underlying IEEE implementation.
You'll have a certain cutoff above which your system bombs.

>>> float(1<<1023)
8.98846567431158e+307
>>> float(1<<1024)
Traceback (most recent call last):
  File "<pyshell#68>", line 1, in <module>
    float(1<<1024)
OverflowError: long int too large to convert to float

(The exact cutoff may depend on how your Python is built, I think;
that was running on a 32-bit Python on Windows.)

Everything else in your code will work, so your only problem is this
square rooting. So here's an alternative:

        for x in range(3, n, 2):
                div, mod = divmod(n, x)
                if mod == 0:
                        return False
                if div < n:
                        break

Once the quotient is lower than the divisor, you've passed the square
root. (Note the use of divmod to do a single division and return both
quotient and remainder. You could alternatively use // and % but it'd
divide twice.)

By the way, the "== True" in your final condition is redundant. Just
test "if isNumberPrime:", or even just "if isprime(a):". :) Though
with something like this that simply returns boolean, I'd be inclined
to make it return a bit more - for instance, it returns the first-seen
factor.

        if n < 2:
                return 1 # Only way this will ever return a non-prime integer
        if n == 2:
                return None # Prime!
        if not n & 1:
                return 2
        # and inside the loop: "return x"

Rename the function to "iscomposite", because prime numbers return
None (false) and composites return a positive integer (true), and
you've just made the function that bit more useful. :)

ChrisA