首页 > 试题广场 >

筛选法求素数

[编程题]筛选法求素数

热度指数：29761 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 使用下方所描述的筛选法，求解 $n$ 以内的全部素数，同时输出被置为 $0$ 的整数个数。

$\hspace{15pt}$ 筛选法求解的过程为：
${\hspace{20pt}}_\texttt{1.}\,$ 将 $2$ 到 $n$ 之间的整数放在数组内存储；
${\hspace{20pt}}_\texttt{2.}\,$ 将数组中 $2$ 之后的所有能被 $2$ 整除的数置为 $0$ ；
${\hspace{20pt}}_\texttt{3.}\,$ 将数组中 $3$ 之后的所有能被 $3$ 整除的数置为 $0$ ；
${\hspace{20pt}}_\texttt{4.}\,$ ……；以此类推，直到将数组中 $n$ 之后的所有数都置为 $0$ 为止；
${\hspace{20pt}}_\texttt{5.}\,$ 此时，数组中剩余的非 $0$ 的数即为 $n$ 以内的全部素数。

【名词解释】
$\hspace{15pt}$ 素数：也称质数。一个大于 $1$ 的正整数，如果除了 $1$ 和它自身以外不再有其他因数，那么这个数被称作素数。特殊地， $1$ 既不是素数也不是合数。

输入描述:

在一行上输入一个整数 。

输出描述:

第一行输出若干个整数，表示  以内的全部素数，用空格分隔。
第二行输出一个整数，表示被置为  的整数个数。

示例1

输入

输出

2 3 5 7 11 13 17 19
11

算法知识视频讲解

Python 3

新的一天，啦啦啦

n = int(input())
res_list = [2]
    
def isNum(number):
    flag = True
    for i in range(2, number):
        if number % i == 0:
            flag = False
    return flag

for i in range(3, n+1, 2):
    is_num = isNum(i)
    if is_num:
        res_list.append(i)

print(*res_list)
print(n - len(res_list) - 1)

发表于 2022-07-11 09:51:50 回复(0)

Python 3

杭研行者

n=int(input())
if n>=7:
    c=[2,3,5,7]
    count=-4
elif 5<=n<7:
    c=[2,3,5]
    count=-3
elif 3<=n<5:
    c=[2,3]
    count=-2
elif 2<=n<3:
    c=[2]
    count=-1
else :
    c=[]
    count=0
for i in range(2,n+1):
    if i%2==0&nbs***bsp;i%3==0&nbs***bsp;i%4==0&nbs***bsp;i%5==0&nbs***bsp;i%6==0&nbs***bsp;i%7==0&nbs***bsp;i%8==0&nbs***bsp;i%9==0:
        count+=1
    else:
        c.append(i)

print(*c)
print(count)

傻瓜解法

发表于 2022-04-29 15:50:53 回复(0)

Python 3

danspace

num = int(input())
l = list(range(2,num+1))

def check_prime(n):
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

res = []
count = 0

for n in l:
    if check_prime(n):
        res.append(n)
    else:
        count += 1
        
print(' '.join(map(str,res)))
print(count)

发表于 2022-03-28 13:35:30 回复(0)

Python 3

溪云初起日沉阁

def prime(n):
    for i in range(2,n):# 优化写法 n ==> int(n**0.5)+1
        if n%i ==0 :#只要有任何一次整除了，就不是素数，返回False
            return False
    #如果都没有跳出，就返回正确
    return True


if __name__ == '__main__':
    n = eval(input())
    list_n = [i for i in range(2,n+1)]

    list_new = []
    for i in list_n:
        res = prime(i)
        if res is True:
            list_new.append(i)
    print(*list_new)
    print(len(list_n)-len(list_new))
#爱图图

发表于 2021-11-04 11:52:26 回复(0)

Python 3

牛客115544353号

while True:
    try:
        listx = []
        list1 = []
        list3 = []
        b= 2
        sum = 0
        a = int(input())
        for i in range(2,a+1):
            listx.append(i)
        while b<a+1 : 
            for i in range(2,a+1):
                if i > b and i % b == 0:
                        list1.append(i)
            b += 1
        list3 = list(set(listx) - set(list1))
        #list3.sort()
        for i in list3:
            print(i,end=" ")
        print("")
        print("%d" %(a-len(list3)-1))
    except:
        break

    这个37为啥在第四个出现