Skip to main content
 首页 » 编程设计

python之你能帮我用这个筛子生成更大的素数吗

2025年05月04日8lonelyxmas

所以我创建了一个程序来生成一个数字并检查它是否是素数,但是我想得到一个更大的素数。当前程序可以快速处理高达 2ish 百万的质数。

def is_Prime(num): 
if(num < 2): 
    return False 
elif (num == 2): 
    return True 
 
if(num%2 == 0): 
    return False 
 
for i in range(3, int(num**0.5)+1, 2): 
    if(num%i == 0): 
        return False 
return True 
 
bigPrime = 0; 
for i in range(1000000): 
    possiblePrime = (2*i) +1 
    if(is_Prime(possiblePrime)): 
        bigPrime = possiblePrime 
 
print(bigPrime)  

我写的 bigPrime 部分

possiblePrime = (2*i) + 1 

是我的计算机科学老师告诉我的一种算法,它擅长生成素数。

非常感谢任何对我的 is_Prime 函数或生成算法的帮助。

请您参考如下方法:

这是一个代码,可以在很短的时间内给出素数 87178291199。

首先,我改变了最快的素性测试。首先,我构建了一个低于某个限制的素数列表(在学校你学习埃拉托色尼筛来做到这一点,这里是更有效的算法)。然后,为了检查一个数是否为素数,我检查它是否可以被列表中的任何素数整除。

其次,我改变了你的 possiblePrime。你的候选人都是奇数:如果你只想要一个“大质数”,这就太多了。 好的候选者是梅森数(形式为 2**n - 1)和阶乘(n!-1 或 n!+1) .参见 Wikipedia .您可以在方便时添加其他方式来产生优秀的候选人。

def rwh_primes2(n): 
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188 
    """ Input n>=6, Returns a list of primes, 2 <= p < n """ 
    correction = (n%6>1) 
    n = {0:n,1:n-1,2:n+4,3:n+3,4:n+2,5:n+1}[n%6] 
    sieve = [True] * (n//3) 
    sieve[0] = False 
    for i in range(int(n**0.5)//3+1): 
      if sieve[i]: 
        k=3*i+1|1 
        sieve[      ((k*k)//3)      ::2*k]=[False]*((n//6-(k*k)//6-1)//k+1) 
        sieve[(k*k+4*k-2*k*(i&1))//3::2*k]=[False]*((n//6-(k*k+4*k-2*k*(i&1))//6-1)//k+1) 
    return [2,3] + [3*i+1|1 for i in range(1,n//3-correction) if sieve[i]] 
 
 
LIMIT = 1000000 
PRIME_LIST = rwh_primes2(LIMIT) 
 
# A number is prime if and only if it is not divisible by any prime lower than its square root. 
def is_Prime(num): 
    for i in PRIME_LIST: 
        if i*i> num: 
            return True 
        elif num%i == 0: 
            return False 
    return True 
 
# Return a sorted list of possible primes lower than limit. 
def possiblePrimes(limit): 
    l = [] 
    # 2**i -1 (Mersenne primes) 
    i = 2 
    while(i < limit): 
        l.append(i-1) 
        i *= 2 
    # n! + 1 or n! -1 (Factorial primes) 
    i = 2 
    n = 2 
    while(i < limit): 
        l.append(i-1) 
        l.append(i+1) 
        n += 1 
        i *= n 
    return sorted(list(l)) 
 
bigPrime = 0 
candidates = possiblePrimes(LIMIT*LIMIT) 
for c in candidates: 
    if(is_Prime(c)): 
        bigPrime = c 
 
print(bigPrime)