• 首页
• Python
• 有人知道为什么我的程序不能生成正确数量的素数吗？

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

### 问题描述

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

### 推荐答案

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):
print(m)
if all(n % p != 0 for p in prime_set):
print(n)
i+=1

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))