有人知道为什么我的程序不能生成正确数量的素数吗? [英] Does anyone know why my program doesn't generate the correct amount of prime numbers?

查看:67
本文介绍了有人知道为什么我的程序不能生成正确数量的素数吗?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

print("Number of primes must be greater than 2")
number = int(input("Number of primes: "))
if number < 1:
    print("Invalid input")
    exit()
print(2)
print(3)
i = 0
no_primes = 2
while 1 < 2:
    m = 6 * i - 1
    n = 6 * i + 1
    if (2 ** m) % m == 2:
        print(m)
        no_primes += 1
    if no_primes == number:
        break
    if (2 ** n) % n == 2:
        print(n)
        no_primes += 1
    if no_primes == number:
        break
    i += 1

我的代码使用了素数可以以6n-1或6n+1的形式表示(2和3除外)的事实。我的While循环看起来很奇怪,但我没有使用由两个变量组成的循环(在本例中是no_PRIMES和i)的专业技能。当我生成前1000个素数时,它跳过了几个,以7789结尾,而不是7919。有人知道为什么吗?另外,如果代码看起来是多余的,请原谅。如果是,请说明我可以如何改进

我几周前才开始使用Python,我想您应该知道

推荐答案

我不确定检查(2 ** m) % m == 2(2 ** n) % n == 2是否会给出所有质数。 你有没有比较过更暴力的方法?

print("Number of primes must be greater than 2")
number = int(input("Number of primes: "))
if number < 1:
    print("Invalid input")
    exit()
elif number == 1:
    print(2)
else:
    print(2)
    print(3)
    prime_set = {2,3}
    i = 1
    while len(prime_set) < number:
        m = 6 * i - 1
        n = 6 * i + 1
        if all(m % p != 0 for p in prime_set):
            prime_set.add(m)
            print(m)
        if all(n % p != 0 for p in prime_set):
            prime_set.add(n)
            print(n)
        i+=1

这里是@Aqeel为提高效率而编辑的解决方案:

import time
import math
number = int(input("Number of primes: "))
t_0 = time.time()
if number < 1:
    print("Invalid input")
    exit()
elif number == 1:
    print(2)
else:
    print(2)
    print(3)
    primes = [2, 3]
    i = 1
    while len(primes) < number:
        prime_m = True
        prime_n = True
        m = 6 * i - 1
        n = 6 * i + 1
        sqrt_m = math.sqrt(m)
        sqrt_n = math.sqrt(n)
        for prime in primes:
            if prime > sqrt_m:
                break
            if m % prime == 0:
                prime_m = False
                break
        if prime_m:
            print(m)
            primes.append(m)
        if len(primes) == number:
            break
        for prime in primes:
            if prime > sqrt_n:
                break
            if n % prime == 0:
                prime_n = False
                break
        if prime_n:
            print(n)
            primes.append(n)
        i += 1
t_1 = time.time()
print(f"Found %s prime numbers in %ss" % (number, t_1 - t_0))

这篇关于有人知道为什么我的程序不能生成正确数量的素数吗?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆