CODEWITHSUNDEEP
python
Shubham
Shubham

Reputation: 22307

Does python show problem with really large integers?

I have a code to calculate highest prime factor of 600851475143.

def PRIME(a):                #Check if no is prime
    f = 0
    i = 2
    while(i < a/2):          #No factor of a no can be greater than a/2
        if (a % i == 0):
            f = 1
            break
        i = i + 1

    if(f == 1):
        return 0
    else:
        return 1


def PFIND(a):
    for i in range(1, 100000):   #Iteratively check if the no is prime
        if PRIME(a/2 - i):       #No factor of a no can be greater than a/2.
            if (a % (a/2 - i) == 0):
                return (a/2 - i)
print PFIND(600851475143)

But the code runs on and on and on and does'nt give any output.

Upvotes: 1

Views: 462

Answers (6)

martineau
martineau

Reputation: 123393

Python's long number support is very verbose and well tested, so I doubt that's the problem. One thing I noticed about your code is that it hasn't be optimized at all and computes the value a/2 several times during in each iteration of the loop. However even if you fixed that it would likely still be too slow because finding prime factors can be a very time consuming especially for larger numbers.

For that reason I think the best approach would be to find a better algorithm. Here's code derived from one I found which calculates all the prime factors of a number. I converted it to Python and simplified it to just keep track of the largest factor it finds. It quickly returned the correct answer for your test case, whose prime factors are {71, 839, 1471, & 6857}. 

def maxprimefactor(n):
    """ find the largest prime factor of a positive integer """
    maxfactor = None
    divisor = 2
    while divisor*divisor <= n:
        if n % divisor:
            divisor += 1
        else:
            maxfactor = divisor
            n /= divisor
    if n != 1:
        maxfactor = n

    return maxfactor if maxfactor else 1

print maxprimefactor(600851475143)
# 6857

Upvotes: 0

inspectorG4dget
inspectorG4dget

Reputation: 113905

I wrote some hobby code that has to do with prime numbers in the past, which I've adapted to work for your purposes. Here is the code:

def isPrime(n, primes=[]):
    """ Return True iff n is a prime number.
            If primes is non-empty, return true iff n is co-prime to every number in primes. """

    if not len(primes):
            if n <= 2:
                    return True
            elif n%2 == 0:
                    return False
            else:
                    prime = True
                    for i in range(3, n, 2):
                            if n%i == 0:
                                    prime = False
                    if prime:
                            return True
    else:
            for p in primes:
                    if not n%p:
                            return False
            return True

def next(n, primes):
    """ Return a number p such that
            1. p is co-prime to every number in primes
            2. p>n and p-n is as small as possible"""

    curr = n+1
    while 1:
            if isPrime(curr, primes):
                    return curr
            else:
                    curr += 1

def generate(n):
    """ Yield the first n prime numbers"""

    primes = [2]
    curr = 2
    for _ in range(n-1):
            p = next(curr, primes)
            primes.append(p)
            curr = p
            yield p

def primeNumbers(n):
    """ return a list of prime numbers such that all numbers in the list are at most n
            1 is a prime number"""

    answer = []
    if n <= 2:
            answer.append(n)
    else:
            for i in range(3, n+1, 2):
                    prime = True
                    for p in answer:
                            if i%p == 0:
                                    prime = False
                                    break
                    if prime:
                            answer.append(i)

    return answer

def PFIND(n):
    primes = primeNumbers(n)
    primes.reverse()
    for p in primes:
        if n%p == 0:
            return p

That should do it.

Hope this helps

Upvotes: 0

nakedfanatic
nakedfanatic

Reputation: 3158

I've found that Python does a great job with large integers. As already mentioned, you are using two brute force tests to crack this nut.

Try this:

a = 600851475143
q = 2

while q <= a / 2:
    if not a % q:
        a /= q
        p = q
    else:
        q += 1

print p

Upvotes: 0

dan04
dan04

Reputation: 90985

Your loop condition of

while(i < a/2):

is making your algorithm take O(N) time.

A simple modification will improve this to O(√N).

hi = int(math.sqrt(a) + 1)     # +1 in case of rounding error.
while i <= hi:

Upvotes: 0

Mark Ransom
Mark Ransom

Reputation: 308091

Rather than starting out with a huge number for testing, try your algorithm on smaller numbers. Then try progressively larger numbers. Plot the amount of time the function takes - I'd suggest using the timeit module. Then extrapolate and estimate how long the function will take on the number you're trying.

I think you'll find that your algorithm is taking so long that it looks like it never finishes.

Upvotes: 3

Raph Levien
Raph Levien

Reputation: 5218

Python's support for large integers is fine. I think your problem is that you're doing very slow algorithms for both brute-force finding the factor and testing whether your factor is prime. If you just invert the order of those two tests (ie, test whether it's a factor, then test whether it's prime), it'll go a lot faster.

But perhaps the problem was about using more sophisticated algorithms. Maybe you should use the Rabin-Miller test instead of brute-force.

Upvotes: 8

Related Questions