0

我一直试图让 python 找到一个数字的最高质因数，并且在 11 天后敲了我明显愚蠢的头之后，我准备寻求帮助。

知道为什么这不会返回最高的素数吗？我手动退出程序需要很长时间，或者抱怨python int to large to convert to C long.

任何帮助或建议将不胜感激！谢谢！

def primeCheck(value):
    for x in range(2, int(value / 2) + 1):
        if value % x < 0.1:
            return False
    return True

val = int(raw_input('What number would you like the highest prime factor of?'))
pc = 2
for x in xrange(pc, int((val / pc) + 1)):
    if primeCheck(x) and val % x < 0.1:
        val = val / x
        pc = x
print pc
4

4 回答 4

1

奇怪，因为我今天刚刚阅读了一个可爱的解决方案 - 给你：

Tryptych 的回答

def prime_factors(n):
    "Returns all the prime factors of a positive integer"
    factors = []
    d = 2
    while (n > 1):
        while (n%d==0):
            factors.append(d)
            n /= d
        d = d + 1

    return factors


pfs = prime_factors(1000)
largest_prime_factor = pfs[-1] # The largest (last) element in the prime factor array
于 2013-04-29T21:37:48.037 回答
0

你的素数测试可能会好得多。根据您需要测试的数字有多大，您可以只维护大量的数字。这是一个很好的素数集合。更好的是像 Miller-Rabin 这样的适当测试，请参阅我的代码以获得可以达到非常大限制的确定性版本。

您还可以查看真正的整数分解算法。

于 2013-04-29T01:14:26.820 回答
0

这是我做的一个。它找到从 2 到一个大数的素数。然后它将素数写入文本文件。

import math
length = 1
percentage = 1
startNumber = input('What number would you like to start counting from? (This has to be 2 to work)')
endNumber = input('What number would you like to finish counting to?')
file = open('Primes.txt','r+')
print(2)
for num in range(int(startNumber) + 1,int(endNumber) + 1,2):
    if all(num%i!=0 for i in range(2,int(math.sqrt(num))+1)):
        print(num)
        file.write(str(num) + '\n')
        length += 1
print('There are ' + str(length) + ' primes between ' + str(startNumber) + ' and ' + str(endNumber) + '.')
file.close()

希望这可以帮助 ：-）

于 2018-06-06T11:49:34.063 回答
0

首先，我定义了一个函数，如果数字是素数，则返回 True。

def prime(i):
""" This function finds whether a number is prime or not?"""
val=False
for n in range(2,i):
    if i%n==0:
            break;
else:
    val=True
return val

然后我使用这个函数来找到输入数字的质因数。

for x in range(2,num):
if num%x==0: 
    if prime(x)==True:
        print ("prime factor of {} is {}".format(num,x))

num 是输入的数字。

于 2018-11-17T17:01:39.347 回答