筛选法求素数

[编程题]筛选法求素数

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

用筛选法求n以内的素数。筛选法求解过程为：将2~n之间的正整数放在数组内存储，将数组中2之后的所有能被2整除的数清0，再将3之后的所有能被3整除的数清0 ，以此类推，直到n为止。数组中不为0 的数即为素数。

输入描述:

多组输入，每行输入一个正整数（不大于100）。

输出描述:

针对每行输入的整数n，输出两行，第一行，输出n之内（包括n）的素数，用空格分隔，

第二行，输出数组中2之后被清0 的个数。每行输出后换行。

示例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为啥在第四个出现