0

13195の素因数は5、7、13、29です。数600851475143の最大の素因数は何ですか？

さて、私はPythonでプロジェクトオイラー問題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を除算するので、13195の係数として5を出力し、元の数を2639 = 13195/5に減らし、5を試します。また。ここで、2639を5で割ると余りが4になるので、6に進み、余りが5になります。次に、7に進むと、2639が除算されるので、7を2639の因数として出力します（また、 13195）そして元の数を再び377 = 2639/7に減らします。ここで7を再試行しますが、8、9、10、11、12と同様に、377を除算できませんが、13は2639を除算します。したがって、13を377（および2639と13195）の約数として出力し、元の数を再び29 = 377/13に減らします。この時点で、試行除数の2乗はまだ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

整数を因数分解するより良い方法があります。しかし、この方法は、プロジェクトオイラー＃3や、他の多くの因数分解プロジェクトにも十分です。素数と因数分解について詳しく知りたい場合は、ブログで「素数を使ったプログラミング」というエッセイをお勧めします。このエッセイには、上記のアルゴリズムのPython実装が含まれています。

于 2012-10-22T02:07:12.313 に答える
6
  • その数600851475143は、ブルートフォースを使用することを思いとどまらせるために大きいです。
  • 数字oddNumbersを入れる関数、それはたくさんのメモリです。600851475143 / 2odd_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 
'''
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

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 
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 に答える
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 に答える