埃式筛法求质数-白红宇

埃式筛法求质数

阅读量：3951 次

发布时间：2019-05-24

本文共 991 字，大约阅读时间需要 3 分钟。

参考资料

给定一个正整数n，请你求出1~n中质数的个数。

输入格式

共一行，包含整数n。

输出格式

共一行，包含一个整数，表示1~n中质数的个数。

数据范围

1≤n≤106

输入样例：

#include 
   
    #include 
    
     #include 
     
      using namespace std;const int N=1e6+10;bool vis[N];int res;void get_primes(int n) {
       for (int i=2;i<=n;++i) {
           if (!vis[i]) {
               for (int j=2;j*i<=n;++j) {
                   vis[j*i]=true;            }            ++res;        }                    }}int main() {
       int n;cin>>n;    get_primes(n);    cout << res;}

解法二：

#include 
   
    #include 
    
     #include 
     
      using namespace std;const int N=1e6+10;bool vis[N];int primes[N];int  _end;void get_primes(int n) {
       for (int i=2;i<=n;++i) {
           if (!vis[i]) primes[_end++]=i;        for (int j=0; primes[j] <= n/i;++j) {
               vis[primes[j]*i] = true;            //如果是倍数，前面赋值过了            if (i % primes[j] ==0) break;        }                    }}int main() {
       int n;cin>>n;    get_primes(n);    cout << _end;}

转载地址：http://ryyzi.baihongyu.com/

你可能感兴趣的文章