题解 1084: 用筛法求之N内的素数

来看看其他人写的题解吧!要先自己动手做才会有提高哦! 
返回题目 | 我来写题解

筛选

【埃式筛法】大幅降低复杂度 -题解(Python代码)

解题思路:用已经筛选出来的素数去过滤所有能够被它整除的数。这些素数就像是筛子一样去过滤自然数,最后被筛剩下的数自然就是不能被前面素数整除的数,根据素数的定义,这些剩下的数也是素数。算法思路:创建两个数组,一个数组放找到的素数(prime),一个用来判断素数(is_prime)。

思路简单的来解决用筛法求之N内的素数。 -题解(C语言代码)

素数是指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数。首先,我的思路是遍历2到N之间的所有数,然后再逐个判断哪一个是素数。因为把一个数分解成两个因数一定会有一个小于它的平方根,所以我只要在2到sqrt(N)就行了。再就是输出素数,我用了flag来标记筛选。