最大质因数Python

问题描述 投票：0回答：10

我正在尝试使用 Python 查找给定数字 (600851475143) 的最大质因数。我编写了以下代码，但问题是，它需要很长时间，可能是因为它迭代了列表数百万次。如何优化这个流程？

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))
list python-3.x primes prime-factoring
10个回答
2
投票

如果您只因式分解单个数字 

n
，那么测试从 2 到 
sqrt(n)
（
n
的平方根）的每个数字的简单方法应该可以快速给出最多 1014 的数字的结果。您编写的代码超出了必要的范围。

稍微更好的方法是：

  • 测试 2，然后测试每个奇数
  • 测试 2、3、5，然后测试 6k + 1 和 6k + 5 形式的所有整数，其中 k >= 1
  • 上面的两种方法是轮分解，分别是 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 或更高版本。

出于好奇，这是针对欧拉项目问题 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)

如果您对使用素数进行编程感兴趣，或者您正在寻找一个库来帮助解决涉及素数的欧拉计划问题，我会在我的博客中谦虚地推荐这篇文章，其中包括，除其他外，上述伪代码到 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
投票

尝试：

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
是其最大素数和某个合数的乘积），您将在检查最大素数是否整除它之前除掉它的所有较小因子。

另一个有用的启发式方法是找到数字的平方根，并且仅检查小于该数字的数字：对于 

n > sqrt(number)
来说，不可能 
n
是 
number
的（整数）因数。不过，我喜欢第一种方法。

sike，没有看到有人已经发布了非常相似的解决方案。

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)

的行为
1
投票

这就是我的做法：

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)
1
投票
n=int(input(""))

prime_factors=[]
for i in range(2,int(n**0.5+1)):
  if n%i==0:
    for x in range(2,int(i**0.5+1)): 
      if i%x==0:
        break
    else:
      prime_factors.append(i)
      
print("prime factors are:",prime_factors)
print("largest prime factor is",prime_factors[-1])

输入：600851475143
输出：质因数为：[71, 839, 1471, 6857]
最大的质因数是 6857

0
投票

实际最终程序：使用长除旧法求因子 并仅存储最大/当前因子，直到找到最后一个。

我知道这是一个老问题，但想分享我解决这个问题的方法。

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
投票
# Largest prime factor of a number
def prime_fact(n):
    p=[]
    f=[]
    p.append(1)
    for d in range(2,n+1):
        if n%d==0:
            f.append(d)

    for v in f:
        if (v==1 or v==2):
            p.append(v)
        else:
            for i in range(2,v):
                if v%i ==0:
                    break

            else:
                p.append(v)
    print(f'Factors of the number are {f}')
    print(f'Primefactors are {p}')
    print(f'Largest prime factor is {p[-1]}')
0
投票

你不必获取所有素数，只获取最大的素数。 当我们寻找素数时，最大除数是 sqrt(n)+1，所以这就是我们开始的地方。 此代码运行不到一秒即可得到答案。 一个简单的方法就是将赔率倒数到 3，然后除以 2，例如：

def is_prime(n):  
    if (n <= 3): return n > 1      
    if not (n%6 == 1 or n%6 == 5): return False      
    for p,q in ((i,i+2) for i in range(5,int(n**.5)+1,6)): 
        if (n%p == 0 or n%q == 0):  return False          
    return True  
    
n = 600851475143
start = int(n**.5)+1 
start = start+(1-start%2) # make odd
for i in range(start,3,-2): 
    if n%i == 0 and is_prime(i): # largest prime divisor
        print(i) 
        break
else: 
    if n%2 == 0: 
        print (2)
    else:
        print(n) # n is prime number

有库方法可以做到这一点。 如果你想要的只是答案。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.