0

13195 的质因数是 5、7、13 和 29。数字 600851475143 的最大质因数是多少？

好的，所以我正在研究 python 中的项目 euler 问题 3。我有点困惑。我不知道我从这个程序中得到的答案是否正确。如果有人能告诉我我做错了什么，那就太好了！

#import pdb

odd_list=[]
prime_list=[2] #Begin with zero so that we can pop later without errors.

#Define a function that finds all the odd numbers in the range of a number
def oddNumbers(x):

  x+=1 #add one to the number because range does not include it
  for i in range(x):
     if i%2!=0: #If it cannot be evenly divided by two it is eliminated
        odd_list.append(i) #Add it too the list
    
  return odd_list 

def findPrimes(number_to_test, list_of_odd_numbers_in_tested_number): # Pass in the prime number to test
   for i in list_of_odd_numbers_in_tested_number:
     if number_to_test % i==0:
       prime_list.append(i)
       number_to_test=number_to_test / i
          
       #prime_list.append(i)
       #prime_list.pop(-2) #remove the old number so that we only have the biggest

       if prime_list==[1]:
           print "This has no prime factors other than 1"
       else:
           print prime_list
       return prime_list
        
    #pdb.set_trace()

    number_to_test=raw_input("What number would you like to find the greatest prime of?\n:")

    #Convert the input to an integer
    number_to_test=int(number_to_test)

    #Pass the number to the oddnumbers function
    odds=oddNumbers(number_to_test)

#Pass the return of the oddnumbers function to the findPrimes function
findPrimes(number_to_test , odds)
4

9 回答 9

7

简单的解决方案是试用除法。让我们处理 13195 的因式分解，然后您可以将该方法应用于您感兴趣的更大数字。

从 2 的试除数开始；13195 除以 2 余数为 1，所以 2 不能除以 13195，我们可以继续下一个试除数。接下来我们尝试 3，但余数为 1；然后我们尝试 4，但余数为 3。下一个试验除数是 5，它确实除以 13195，所以我们输出 5 作为 13195 的因数，将原始数字减少到 2639 = 13195 / 5，然后尝试 5再次。现在 2639 除以 5 余数为 4，所以我们前进到 6，余数为 5，然后我们前进到 7，它确实除以 2639，所以我们输出 7 作为 2639 的因数（也是13195) 并再次将原始数字减少到 377 = 2639 / 7。现在我们再次尝试 7，但它不能除以 377，就像 8、9、10、11 和 12 一样，但是 13 可以除以 2639。所以我们输出 13 作为 377（以及 2639 和 13195）的除数，然后再次将原始数字减少到 29 = 377 / 13。至此我们完成了，因为仍然是 13 的试验除数的平方是大于剩下的数 29，证明 29 是素数；之所以如此，是因为如果n=pq，那么p或q必须小于或等于 n 的平方根，并且由于我们已经尝试了所有这些除数，因此剩余的数字 29 必须是素数。因此，13195 = 5 * 7 * 13 * 29。

这是算法的伪代码描述：

function factors(n)
    f = 2
    while f * f <= n
        if f divides n
            output f
            n = n / f
        else
            f = f + 1
    output n

有更好的方法来分解整数。但是这种方法对于 Project Euler #3 以及许多其他分解项目来说已经足够了。如果你想了解更多关于素数和因式分解的知识，我建议在我的博客上写一篇用素数编程的文章，其中包括上述算法的 python 实现。

于 2012-10-22T02:07:12.313 回答
6
  • 这个数字600851475143很大，不鼓励你使用蛮力。
  • oddNumbers将600851475143 / 2数字放入的功能odd_list，这是很多内存。
  • 检查一个数字可以被奇数整除并不意味着奇数是质数。您提供的算法是错误的。
  • 有很多关于素数的数学/算法技巧，你应该在网上搜索它们，然后筛选答案。您也可能会找到问题的根源，以确保您已经解决了一些问题。

您可以使用生成器来获取赔率列表（不是说它会帮助您）：

odd_list = xrange(1, number+1, 2)

以下是处理素数所需的概念：

如果你真的被卡住了，那么已经有解决方案了：

于 2012-10-21T16:52:20.717 回答
1

这是我的 Python 代码：

num=600851475143
i=2 # Smallest prime factor
for k in range(0,num):
    if i >= num: # Prime factor of the number should not be greater than the number
        break
    elif num % i == 0: # Check if the number is evenly divisible by i
        num = num / i
    else:
        i= i + 1
print ("biggest prime number is: "+str(num))
于 2017-12-18T12:49:43.213 回答
0

这是我的python代码：

import math
ma = 600851475143
mn = 2
s = []
while mn < math.sqrt(ma):
    rez = ma / mn
    mn += 1
    if ma % mn == 0:
        s.append(mn)
print(max(s))
于 2019-12-22T10:26:58.630 回答
0 
def prime_max(x):
a = x
i = 2
while i in range(2,int(a+1)):
    if a%i == 0:
        a = a/i
        
        if a == 1:
             print(i)
        i = i-1
    i = i+1
于 2020-09-01T08:03:14.677 回答
0

使用 Python 解决此问题的另一种方法。

def lpf(x):
lpf=2
while (x>lpf):
    if (x%lpf==0):
        x=x/lpf

    else:
        lpf+=1
return x
print(lpf(600851475143))
于 2018-01-30T15:18:22.670 回答
0 
'''
The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?
'''
import math

def isPrime(x):
    if x<2:
        return False
    for i in range(2,int(math.sqrt(x))):
        if not x%i:
           return False
    return True

def largest_factor(number):
    for i in range (2, int(math.sqrt(number))):
        if number%i == 0:
            number = number/i
            if isPrime(number) is True:
                max_val = number
                break
                print max_val
        else:
            i += 1
    return max_val

largest_factor(600851475143)

这实际上编译得非常快。它检查形成的数字是否为质数。谢谢

于 2016-10-06T03:02:03.587 回答
0 
i = 3
factor = []
number = 600851475143
while i * i <= number:
    if number % i != 0:
        i += 2
    else:
        number /= i
        factor.append(i)
while number >= i:
    if number % i != 0:
        i += 2
    else:
        number /= i
        factor.append(i)
print(max(factor))
于 2018-05-07T00:21:13.887 回答
0

这是我的python代码

a=2
list1=[]
while a<=13195:                     #replace 13195 with your input number
    if 13195 %a ==0:                #replace 13195 with your input number
        x , count = 2, 0
        while x <=a:
            if a%x ==0:
                count+=1
            x+=1
        if count <2:
            list1.append(a)
    a+=1

print (max(list1))
于 2018-10-13T07:30:54.597 回答