找到大量最大素数的有效方法

问题描述

我正在我发现的站点(Euler项目)上解决此问题，并且存在一个问题，其中涉及寻找数字中最大的素因数.我的解决方案大量失败，所以我想知道如何简化此代码?

I'm doing this problem on a site that I found (project Euler), and there is a question that involves finding the largest prime factor of a number. My solution fails at really large numbers so I was wondering how this code could be streamlined?

""" Find the largest prime of a number """


def get_factors(number):
    factors = []
    for integer in range(1, number + 1):
        if number%integer == 0:
            factors.append(integer)
    return factors

def test_prime(number):
    prime = True
    for i in range(1, number + 1):
        if i!=1 and i!=2 and i!=number:
            if number%i == 0:
                prime = False
    return prime

def test_for_primes(lst):
    primes = []
    for i in lst:
        if test_prime(i):
            primes.append(i)
    return primes


################################################### program starts here
def find_largest_prime_factor(i):
    factors = get_factors(i)
    prime_factors = test_for_primes(factors)
    print prime_factors


print find_largest_prime_factor(22)

#this jams my computer
print find_largest_prime_factor(600851475143)

使用大数时失败，这是我猜到的问题所在. (计算机出现故障，告诉我我的内存已用完，并询问我要停止哪些程序).

it fails when using large numbers, which is the point of the question I guess. (computer jams, tells me I have run out of memory and asks me which programs I would like to stop).

************************************ 谢谢您的回答.在任何情况下，代码中实际上都有几个错误.因此，此(无效代码)的固定版本如下.

************************************ thanks for the answer. there was actually a couple bugs in the code in any case. so the fixed version of this (inefficient code) is below.

""" Find the largest prime of a number """


def get_factors(number):
    factors = []
    for integer in xrange(1, number + 1):
        if number%integer == 0:
            factors.append(integer)
    return factors

def test_prime(number):
    prime = True
    if number == 1 or number == 2:
        return prime
    else:
        for i in xrange(2, number):
            if number%i == 0:
                prime = False
    return prime


def test_for_primes(lst):
    primes = []
    for i in lst:
        if test_prime(i):
            primes.append(i)
    return primes


################################################### program starts here
def find_largest_prime_factor(i):
    factors = get_factors(i)
    print factors
    prime_factors = test_for_primes(factors)
    return prime_factors


print find_largest_prime_factor(x)

推荐答案

根据您的方法，首先在O(n)中生成所有数字n的除数，然后测试在另一个O(n)中哪个除数是质数test_prime的调用次数(反正是指数).

From your approach you are first generating all divisors of a number n in O(n) then you test which of these divisors is prime in another O(n) number of calls of test_prime (which is exponential anyway).

一种更好的方法是观察到，一旦找到一个数的除数，就可以反复除以该数，以消除所有的因数.因此，要获得830297的素数因子，您要测试所有小的素数(已缓存)，对于每一个除以您的数的素数，您都应保持除法.

A better approach is to observe that once you found out a divisor of a number you can repeatedly divide by it to get rid of all of it's factors. Thus, to get the prime factors of, say 830297 you test all small primes (cached) and for each one which divides your number you keep dividing:

• 830297可被13整除，因此现在您将使用830297 / 13 = 63869
进行测试
• 63869仍可被13整除，您在4913
• 4913不除以13，下一个质数是17，它将4913除以得到289
• 289仍然是17的倍数，您有17这是除数和终止点.

• 830297 is divisible by 13 so now you'll test with 830297 / 13 = 63869
• 63869 is still divisible by 13, you are at 4913
• 4913 doesn't divide by 13, next prime is 17 which divides 4913 to get 289
• 289 is still a multiple of 17, you have 17 which is the divisor and stop.

为了进一步提高速度，在测试了下面说100的缓存素数后，您必须使用test_prime函数(根据@Ben的答案更新)测试素数除数，但反过来，从sqrt.您的数字可被71整除，下一个数字将给出sqrt的91992，该数字与最大素数的6857有点接近.

For further speed increase, after testing the cached prime numbers below say 100, you'll have to test for prime divisors using your test_prime function (updated according to @Ben's answer) but go on reverse, starting from sqrt. Your number is divisible by 71, the next number will give an sqrt of 91992 which is somewhat close to 6857 which is the largest prime factor.

这篇关于找到大量最大素数的有效方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！