Geek asks and answers

Finding the largest prime divisor (the fastest program possible)

I checked for problems at http://projecteuler.net/

The third problem is this:

The main factors of 13195 are 5, 7, 13 and 29. What is the largest simple coefficient of the number 600851475143?

My solution code is below. But it is so slow that I think it will take several weeks. How can I improve it? Or is Python too much to solve this problem?

def IsPrime(num):
    if num < 2:
        return False
    if num == 2:
        return True
    else:
        for div in range(2,num):
            if num % div == 0:
                return False
        return True

GetInput = int (input ("Enter the number: "))


PrimeDivisors = []

for i in range(GetInput, 1, -1):
    print(i)
    if GetInput % i == 0 and IsPrime(i) is True:
        PrimeDivisors.append(i)
        break
    else:
        continue


print(PrimeDivisors)
print("The greatest prime divisor is:", max(PrimeDivisors))
+1
source share
4 answers

The problem with your decision is that you do not take into account the found main factors, so you unnecessarily check the factors after you really find the biggest one. Here is my solution:

def largest_prime_factor(n):
    largest = None

    for i in range(2, n):
        while n % i == 0:
            largest = i
            n //= i

        if n == 1:
            return largest

    if n > 1:
        return n

Project Euler , , , , , , .

, , . .

+2

, :

def prime(x):
    if x in [0, 1]:
        return False
    for n in xrange(2, int(x ** 0.5 + 1)):
        if x % n == 0:
            return False
    return True

def primes():
    """Prime Number Generator

    Generator an infinite sequence of primes

    http://stackoverflow.com/questions/567222/simple-prime-generator-in-python
    """

    # Maps composites to primes witnessing their compositeness.
    # This is memory efficient, as the sieve is not "run forward"
    # indefinitely, but only as long as required by the current
    # number being tested.
    #
    D = {}  

    # The running integer that checked for primeness
    q = 2  

    while True:
        if q not in D:
            # q is a new prime.
            # Yield it and mark its first multiple that isn't
            # already marked in previous iterations
            # 
            yield q        
            D[q * q] = [q]
        else:
            # q is composite. D[q] is the list of primes that
            # divide it. Since we've reached q, we no longer
            # need it in the map, but we'll mark the next 
            # multiples of its witnesses to prepare for larger
            # numbers
            # 
            for p in D[q]:
                D.setdefault(p + q, []).append(p)
            del D[q]

        q += 1

def primefactors(x):
    if x in [0, 1]:
        yield x
    elif prime(x):
        yield x
    else:
        for n in primes():
            if x % n == 0:
                yield n
                break
        for factor in primefactors(x // n):
            yield factor

:

>>> list(primefactors(100))
[2, 2, 5, 5]
+1

, . collection.defaultdict() primes() , , - .

def primes():
    """Prime number generator."""
    n, skip = 2, {}
    while True:
        primes = skip.get(n)
        if primes:
            for p in primes:
                skip.setdefault(n + p, set()).add(p)
            del skip[n]
        else:
            yield n
            skip[n * n] = {n}
        n += 1

def un_factor(n):
    """Does an unique prime factorization on n.

    Returns an ordered tuple of (prime, prime_powers)."""
    if n == 1:
        return ()
    result = []
    for p in primes():
        (div, mod), power = divmod(n, p), 1
        while mod == 0:
            if div == 1:
                result.append((p, power))
                return tuple(result)
            n = div
            div, mod = divmod(n, p)
            if mod != 0:
                result.append((p, power))
            power += 1

:

>>> un_factor(13195)
((5, 1), (7, 1), (13, 1), (29, 1))
>>> un_factor(600851475143)
((71, 1), (839, 1), (1471, 1), (6857, 1))
>>> un_factor(20)
((2, 2), (5, 1))

EDIT: primes() .

EDIT2: 20.

3: _prime_divisor() un_factor().

+1
source 
def getLargestFactor(n):
    maxFactor = sqrt(n)
    lastFactor = n
    while n%2 == 0:
        n  /= 2
        lastFactor = 2
    for i in xrange(3,int(maxFactor),2 ):
        if sqrt(n) < i:
             return n
        while n%i == 0 and n > 1:
            n  /= i
            lastFactor = i
    return lastFactor

This should be quite effective. Separating each factor, in this way we find only the main factors. And using the fact that there can only be one simple coefficient of a number greater than sqrt (n).

0
source

More articles:


All Articles