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

这段代码的工作方式是:

• 从数到5个素数开始计数
• 数字前倒数直到5个素数(在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素数测试):

如何创建到极限n的最紧映射n→isprime(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分钟。