PAT03：数素数

3.数素数

题目

题目描述

1
令Pi表示第i（i从1开始计数）个素数。现任给两个正整数M <= N <= 10000，请输出PM到PN的所有素数。

输入描述:

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

输出描述:

1
输出从PM到PN的所有素数，每10个数字占1行，其间以空格分隔，但行末不得有多余空格。

输入例子:

1
5 27

输出例子:

1
2
3
11 13 17 19 23 29 31 37 41 43
47 53 59 61 67 71 73 79 83 89
97 101 103

题解

(1)我的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import sys

def suShu(num):
    if num <= 1:
        return False
    n = int(num**0.5) + 1
    for i in range(2,n+1):
        if num % i == 0 and num != i:
            return False
    return True 

def outNum(nums):
    for i,num in enumerate(nums,start=1):
        if i % 10 == 0:
            print(num)
        else:
            if i == len(nums):
                print(num,end='')
            else:
                print(num,end=' ')
    

for line in sys.stdin:
    res = []
    m,n = map(int,line.split())
    num = 1
    count = 0
    while True:
        num += 1
        if suShu(num):
            count += 1
            if m<=count<=n:
                res.append(num)
            elif count > n:
                break
    outNum(res)

（2）其他解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from math import sqrt
import sys

def isPrime(x):
    for i in range(2, int(sqrt(x))+1):
        if x % i == 0:
            return False
    return True

for line in sys.stdin:
    no = line.split(' ')
    m, n = int(no[0]), int(no[1])
    i,count = 2,0
    while count < n :
        if isPrime(i):
            count += 1
            if count >= m:
                if (count-m+1)%10 != 0:
                    print(i,end=' '),
                else :
                    print(i)
        i += 1

知识点

素数（质数）

指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

1
2
3
4
5
def isPrime(x):
    for i in range(2, int(sqrt(x))+1):
        if x % i == 0:
            return False
    return True

打印分隔符

打印结束时使用的行尾符号，默认是换行符 \n。

sep是间隔中有符号，末尾不会有符号

1
print(item1, item2, item3, sep=' 分隔符 ')

end是每个元素后面都有符号，末尾也会有

1
print(item1, item2, end=' 结尾符 ')

每10个处理一次

1、结果列表中的元素索引 % 10 == 0

2、（输出序数-输出开始数+1）%10 == 0

开根

1
num**0.5
1
2
from math import sqrt
sqrt(num)