Python程序查找给定整数上下5个素数

Question

我在编写一个程序时遇到了问题，该程序在用户输入的整数“n”上下查找5个素数

注：如果少于5个素数，则打印数量应尽可能小。如果n本身是素数，则不应包含它。不允许使用列表或函数

这是我应该得到的输出：

Please enter n: 20
Larger prime numbers: 23 29 31 37 41
Smaller prime numbers: 19 17 13 11 7

这是我的尝试：

n = int(input("Number: "))
# n = 20
count1 = 0
x = 2

while count1<5:
    for i in range(2, n+x):
        if (n+x) % i ==0:
            break
        else:
            print(n+x)
            count1 += 1
            break
    x +=1

Answer 1

此代码通过以下方式工作：

• 数到五个素数后再计数
• 计数前倒计时，直到达到五个素数（在2处停止）
• 不使用任何函数或列表（除我认为可以使用的模函数）

代码

n = int(input('Please enter n: '))
# Try larger numbers than n
print('Larger prime numbers:', end = ' ')
num = n + 1
cnt = 0
while True:
    for i in range(2, num-1):     # prime test
        if num % i == 0:
            break
    else:
        print(num, end = ' ')     # was prime
        cnt += 1
        if cnt == 5:
            break
    num += 1

# Try smaller numbers than n
print('\nSmaller prime numbers:', end = ' ')
cnt = 0
num = n - 1
while num > 1:
    for i in range(2, num-1):    # prime test
        if num % i == 0:
            break
    else:
        print(num, end = ' ')    # was prime
        cnt += 1
        if cnt == 5:
            break
            
    num -= 1

测试

Please enter n: 20
Larger prime numbers: 23 29 31 37 41 
Smaller prime numbers: 19 17 13 11 7 
​

Answer 2

这篇文章中的答案提供了一个优秀的函数形式来测试素性（AKS素性测试）：

How to create the most compact mapping n → isprime(n) up to a limit N?

而且测试不需要找到任何素数的“记忆”

然后，任务是对该函数进行编码，而不使其成为实际函数

n = int(input("Number: "))
M=5

print(f'{M} primes below {n}: ',end='')
itest=n-n%2-1 # number is odd, and is below input number
nab=0
while nab<M:
  if itest == 2:
    print(itest,end=' ')
    nab+=1
    break
  if itest == 3:
    print(itest,end=' ')
    nab+=1
    itest-=1
    continue
  if itest % 2 == 0:
    itest-=2
    continue
  if itest % 3 == 0:
    itest-=2
    continue

  i = 5
  w = 2

  ipass=True
  while i * i <= itest:
    if itest % i == 0:
      ipass=False
      break
    i += w
    w = 6 - w
  if ipass:
    print(itest,end=' ')
    nab+=1
  itest-=2

print('')

print(f'{M} primes above {n}: ',end='')
itest=n+n%2+1 # number is odd, and is above input number
nab=0
while nab<M:
  if itest == 2:
    print(itest,end=' ')
    nab+=1
    itest+=2
    continue
  if itest == 3:
    print(itest,end=' ')
    nab+=1
    itest+=2
    continue
  if itest % 2 == 0:
    itest+=2
    continue
  if itest % 3 == 0:
    itest+=2
    continue

  i = 5
  w = 2

  ipass=True
  while i * i <= itest:
    if itest % i == 0:
      ipass=False
      break
    i += w
    w = 6 - w
  if ipass:
    print(itest,end=' ')
    nab+=1
  itest+=2

例如，22的输出为

Number: 22
5 primes below 22: 19 17 13 11 7
5 primes above 22: 23 29 31 37 41

还有一个例子：

Number: 131553423669295
5 primes below 131553423669295: 131553423669257 131553423669181 131553423669097 131553423669043 131553423668977
5 primes above 131553423669295: 131553423669299 131553423669347 131553423669413 131553423669419 131553423669439

时间测试

对于较大的数字，此算法的速度要快得多

例如，对数字5564445的该算法进行timeit测试，执行1000次，耗时2.66秒。用简单的方法除以每个数字直到找到一个除数，需要1小时40分钟