解题思路:
用已经筛选出来的素数去过滤所有能够被它整除的数。这些素数就像是筛子一样去过滤自然数,最后被筛剩下的数自然就是不能被前面素数整除的数,根据素数的定义,这些剩下的数也是素数。
算法思路:
创建两个数组,一个数组放找到的素数(prime),一个用来判断素数(is_prime)。
用来判断素数的列表用is_prime=[True]*(n+1)生成
生成后的样子[True,True,True,True,True...]
之后从2到n+1开始1循环,将i代入is_prime列表
如果当前i是True,该数为素数
将其放到素数数组内,然后进入2循环
如果当前i是False则直接进入2循环
2循环中依次取i的倍数(不算i),将其变成False
这样每次1循环循环到i的倍数,将不会执行append()
参考代码:
#埃拉托什尼
n=int(input()) primes=[] alist=[True]*(n+1) #创建一个有n+1个True的列表 for i in range(2,n+1): if alist[i]: #将i代入is_prime列表中,如果true则执行,如果false则不执行 primes.append(i) #用当前素数i去筛掉所有能被它整除的数 for j in range(i*2,n+1,i): #依次取i的倍数; 从i*2开始循环到n+1,步长为i; alist[j]=False for i in range(len(primes)): print(primes[i])
0.0分
16 人评分
C语言程序设计教程(第三版)课后习题9.8 (C语言代码)浏览:1206 |
K-进制数 (C++代码)浏览:858 |
简单编码 (C++代码)浏览:678 |
C二级辅导-公约公倍 (C语言代码)浏览:1510 |
A+B for Input-Output Practice (C++代码)浏览:609 |
C语言程序设计教程(第三版)课后习题5.6 (C语言代码)浏览:867 |
【矩阵】 (C++代码)浏览:950 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:473 |
Cylinder (C语言描述,蓝桥杯)浏览:1247 |
C语言程序设计教程(第三版)课后习题3.7 (C语言代码)浏览:569 |