筛法求素数
程序员文章站
2024-03-15 13:02:05
...
又到了培训新生的季节,昨天新生中的某位大佬突然问到筛法求素数的问题,让我这个每次都用最傻逼的暴力循环求素数的老腊肉声泪俱下,反思了一下自己根本不会筛法求素数,于是决定补上。
说出来怕大家笑话,学习前,我是这么求素数的
#include<bits/stdc++.h>
using namespace std;
int func(int n) {
int count = 0;
for(int i = 2; i < n; i++) {
if(n % i == 0)
break;
else count++;
}
if(count == n - 2)
return 1;
else return 0;
}
int main () {
int n;
cin >> n;
if(func(n))
cout << "prime" << endl;
else cout << "no" << endl;
return 0;
}
真是尴尬,这是按照定义来的,虽然func里的n可以优化一下改成sqrt(n),不过以前写题就是为了题量,现在目的不一样了,追求更优。
所以,来说筛法求素数吧。
学习了一下埃氏筛法求素数(给新生看的)
基本思路是:素数的倍数不是素数
那行了道理大家都懂,该咋写呢?
实现方法是:
用一个bool型的prime数组memset成0,即一开始假设所有的数都是素数(如果不会memset就用for循环遍历一遍全部初始化成0), 然后现在我们有两个已知的非素数(合数)prime[0], prime[1]就将它们初始化成1
2是第一个素数吧,没问题吧?那现在开始了,循环一遍,把2的倍数全部初始化成1,如果2的某个倍数已经超过了我们给的范围, 就结束循环
接下来找离2最近的素数,3吧,没问题吧?再执行上个循环,3的倍数也变成1了,再从3后面找,4已经被改成1了,那就是5了……
后面一直循环就完了
然后主函数里调用一下,输出!prime[i],的i。范围内所有的素数都出来了吧,贴上代码看起来方便。
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5;
bool prime[MAXN];
void eratosthense(){
memset(prime, 0, sizeof(prime));
int m = sqrt(MAXN);
prime[0] = prime[1] = 1;
for(int i = 2; i <= m; i++){
if(prime[i]){
continue;
}
for(int j = i; j * i < MAXN; j++){
prime[i * j] = 1;
}
}
}
int main(){
eratosthense();
for(int i = 0; i < MAXN; i++){
if(!prime[i]){
cout << i << " ";
}
}
return 0;
}
行了,这个学完了,相比一开始的傻瓜式求素数已经进化很多了
当然还有更好的筛法,以后单独说,吸吸。