信息学奥赛一本通 2040

【例5.7】筛选法找质数

【题目描述】
用筛法求出n(2≤n≤1000)以内的全部质数。

【输入】
无。

【输出】
一行，为n以内全部质数，每个质数后面有一个空格，最后一个质数后面没有空格。如果n以内没有质数，输出一行空行。

【输入样例】
无。

【输出样例】
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

1.筛选法

n = 1000
is_prime = [True] * (n+1) # 初始化所有数为质数
is_prime[0], is_prime[1] = False, False # 0和1不是质数
for i in range(2, int(n**0.5)+1): # 从2到根号n遍历
    if is_prime[i]: # 如果i是质数
        for j in range(i*i, n+1, i): # 将i的倍数标记为合数
            is_prime[j] = False
for i in range(2, n+1): # 输出所有质数
    if is_prime[i]:
        print(i, end=' ')

2.函数法

import sympy

n = 1000
for i in range(2, n+1):
    if sympy.isprime(i): # 使用sympy库中的isprime函数判断是否为质数
        print(i, end=' ')

3.sqrt法

import math

n = 1000
for i in range(2, n+1):
    is_prime = True
    for j in range(2, int(math.sqrt(i))+1): # 从2到根号i遍历
        if i % j == 0: # 如果i能被j整除，说明i不是质数
            is_prime = False
            break
    if is_prime:
        print(i, end=' ')