PAT (Basic Level) Practice （中文）1013 数素数 （20 分)

题目

令 P​_i​ 表示第 i 个素数。现任给两个正整数 M≤N≤10​⁴​ ，请输出 P​_M​ 到 P​_N​ 的所有素数。

输入格式：

输入在一行中给出 M 和 N，其间以空格分隔。

输出格式：

输出从 P

​M

​​ 到 P

​N

​​ 的所有素数，每 10 个数字占 1 行，其间以空格分隔，但行末不得有多余空格。

输入样例：

5 27

输出样例：

11 13 17 19 23 29 31 37 41 43

47 53 59 61 67 71 73 79 83 89

97 101 103

C++实现

#include <iostream>
#include <cstring>
using namespace std;
bool is_prime(int num)
{
for (int i = 2; i*i <= num; ++i) {
if (num%i==0) return false;
}
return true;
}
int main()
{
int m,n;
cin>>m>>n;
int index=0,c=0;
long long num=2;
while (index<n)
{
if (is_prime(num))
{
index++;
if (index>=m)
{
cout << num; c++;
if (index<n&&c<10) cout<<' ';
if (c==10)
{
c=0;
cout<<endl;
}
}
}
num+=1;
}
return 0;
}

python实现

import math
def is_prime(num):
if num%2==0 and num!=2:
return False
if num%3==0 and num!=3:
return False
for i in range(4,int(math.sqrt(num)+1)):
if num%i==0:
return False
return True

a=input().split()
m=int(a[0])
n=int(a[1])

index=1
num=2
c=0
while index<=n:
if is_prime(num):
index+=1
if index>m:
print(num,end='')
c+=1
if index<=n and c<10:
print(' ',end='')
if c==10:
c=0
print('\n',end='')
num+=1

这是直接把C++代码转换成python代码来做，但是有一个点会超时，尽管加了一些优化，但还是通不过，也许这就是python吧。

def prime(n,result):
flag = [1]*(n+2)
p=2
while(p<=n):
result.append(p)
for i in range(2*p,n+1,p):
flag[i] = 0
while 1:
p += 1
if(flag[p]==1):
break
a = input().split()
result = []
prime(200000,result)
final = result[int(a[0])-1:int(a[1])]
if len(final)==1:
print(final[0])
else:
for i in range(len(final)-1):
if (i+1)%10==0:
print(final[i])
else:
print(final[i],end=" ")
if (i+2)%10==0:
print(final[i+1])
else:
print(final[i+1],end="")

附上大佬的代码，基本思路就是先把所有的素数都求出来并保存，以空间换时间，然后去切片输出。