时间戳

首页 > 解决方案 > 我应该怎么做才能运行此代码（不更改代码）

python-3.x - 我应该怎么做才能运行此代码（不更改代码）

问题描述

我正在解决关于 Project Euler (Largest Prime Factor) 的第三个问题，我是 Python 3 的初学者。

这是我想出的解决方案，它可以工作，但不能用于非常大的数字

x=int(input("Enter a number:"))
a=[]
for i in range(1,x+1):
    cnt=0
    if x%i==0:
        for j in range(1,i+1):
            if i%j==0:
                cnt=cnt+1
        if cnt==2:
            a.append(i)
print(a[len(a)-1])

我了解它非常基本，并且运行大输入太慢，但是编译器有什么办法可以给我这个输入的输出 - 600851475143。我尝试使用 pypy3，它也花费了太长时间。

这是我第一次使用stackoverflow，所以如果我做错了什么，请告诉我。

标签： python-3.xprime-factoring

解决方案

我知道您说过您不想更改代码，但如果您想有效地解决它，您必须这样做。实际上有一个专门用于此的库，eulerlib但内置math模块也可以做到这一点。

如果你想在没有模块的情况下使用 python，你可以试试这个，但对于大数字来说它可能同样慢

def Largest_Prime_Factor(n):
    prime_factor = 1
    i = 2

    while i <= n / i:
        if n % i == 0:
            prime_factor = i
            n /= i
        else:
            i += 1

    prime_factor = max(prime_factor, n)
    return prime_factor

内置math模块也可以做到这一点，而且速度要快得多。由于它是内置的，因此您不需要任何外部库，例如eulerlib

import math

# Getting input from user
n = int(input("Enter the number : "))

maxPrimeFactor = 0
# Checking and converting the number to odd
while n % 2 == 0:
    maxPrimeFactor = 2
    n = n/2

# Finding and dividing the number by all
# prime factors and replacing maxPrimeFactor
for i in range(3, int(math.sqrt(n)) + 1, 2):
    while n % i == 0:
        maxPrimeFactor = i
        n = n / i
if n > 2:
    maxPrimeFactor = n

print("The largest prime Factor of the number is ",int(maxPrimeFactor))

推荐阅读