Geek asks and answers

Biggest Prime Factor Python

I am trying to find the largest prime coefficient of a given number (600851475143) using Python. I made the following code, but the problem is that it takes forever, perhaps because it iterates through lists millions of times. How to optimize this process?

def factors(n):
    list = []
    i = 1
    while i < n:
        if n % i == 0:
            list.append(i)
        i += 1
    return list

def prime(n):
    list = factors(n)
    primelist = []
    for item in list[1:]:
        if item % 2 != 0 and item % 3 != 0 and item % 4 != 0 and item  \
        % 5 != 0 and item % 6 != 0 and item % 7 != 0 and item % 8 != 0 \
        and item % 9 != 0:
            primelist.append(item)
    return primelist

def greatestprime(n):
    list = prime(n)
    list[0] = lnum
    i = 1
    while i < len(list):
        if list[i] > lnum:
            lnum = list[i]
    return lnum

#print(greatestprime(600851475143))
+3
source share
7 answers

If you only factorize a single number n, then a naive approach to testing each number from 2 to sqrt(n)(the square root of n) should quickly give a result for numbers up to 10 14 . You write more code than necessary.

Slightly better approaches:

  • Test 2, then check every odd number
  • 2, 3, 5, 6k + 1 6k + 5, k >= 1
  • 2 n = 2 n = 2 * 3 = 6 . n = 2 * 3 * 5 * 7 = 210 ( ).

, Eratosthenes ( ). , Pollard rho , , .

+2

, .

from itertools import takewhile
from math import floor, sqrt

def _prime_numbers_helper():
    yield 2
    yield 3
    i = 1
    while True:
        yield 6 * i - 1
        yield 6 * i + 1
        i += 1

def prime_numbers(ceiling=None):
    if ceiling is None:
        yield from _prime_numbers_helper()
    else:
        yield from takewhile(lambda number: number <= ceiling, _prime_numbers_helper())

def largest_prime_factor(number):
    if number % int(number) != 0:
        raise ValueError('The number must be an integer.')
    if number in (0, 1):
        raise ValueError('There is no largest prime factor of {}.'.format(number))

    while True:
        for i in prime_numbers(floor(sqrt(abs(number)))):
            if number % i == 0:
                number //= i
                break
        else:
            return number

else , for (.. ).

for , , .

, , Python 3.3 .

Project Euler Problem 3?

+2

n , n ; :: f fs:

function factors(n)
    f, fs := 2, []
    while f * f <= n
        while n % f == 0
            n := n / f
            fs := f :: fs
        f := f + 1
    if n <> 1
        n :: fs
    return reverse(fs)

, Project Euler, , , , , Python:

def td_factors(n, limit=1000000):
    if type(n) != int and type(n) != long:
        raise TypeError('must be integer')
    fs = []
    while n % 2 == 0:
        fs += [2]
        n /= 2
    if n == 1:
        return fs
    f = 3
    while f * f <= n:
        if limit < f:
            raise OverflowError('limit exceeded')
        if n % f == 0:
            fs += [f]
            n /= f
        else:
            f += 2
    return fs + [n]
+2

. :

def gpf(n):
    """
    Find the greatest prime factor of n
    """
    if n < 2:
        raise ValueError('{} does not have a prime factorization'.format(n))
    divisor = 2
    while n > 1:
        if not n % divisor:
            n /= divisor
            divisor -= 1
        divisor += 1
    return divisor

:

In [15]: gpf(600851475143)
Out[15]: 6857

In [16]: timeit gpf(600851475143)
1000 loops, best of 3: 1.55 ms per loop

SymPy:

from sympy import factorint
def gpf(n):
    return max(factorint(n).keys())

(, n < 2)

+2

:   / , .

, , .

def prime_factors_old_fashioned_factorization(number):
    y=1
    for x in range(2,number):
        if(number%x==0):
            print("number=",number,"\t and X=",x)
            while(number%x==0):
                print("number=",number)
                number=number/x
            print("new number=",number)
            y=x
            x=x+1
            if((number==1) or (number<x)):
                break;
    print("largest prime factor=",y)
0

:

def is_prime(m):
    """Checks if the argument is a prime number."""

    if m < 2: return False

    for i in xrange(2, m):
        if m % i == 0:
            return False

    return True

def get_largest_prime_factor(k):
    """Gets the largest prime factor for the argument."""

    prime_divide = (p for p in xrange(1, k))
    for d in prime_divide:

        if k % d == 0 and is_prime(k / d):
            return k / d

print get_largest_prime_factor(600851475143)
0

Try:

number = whatever your number is
divisor = 2

while divisor < number:
    if number % divisor == 0:
        number /= divisor
    else:
        divisor += 1

, - , ( 12- ). ,

, : , , . 32, , 2 6 , , , number. , , , . (number ) , , .

Another useful heuristic is to find the square root of your number and only check numbers less than this: it is impossible n > sqrt(number)for nwhich are (integer) factors number. However, I like the first method.

sike, did not see that someone had already published a really similar solution.

0
source

More articles:


All Articles