首页 > 代码库 > 两种 eratosthenes 筛法的时间比较，第二种快很多会比较好用

两种 eratosthenes 筛法的时间比较，第二种快很多会比较好用

2024-07-16 22:41:18   219人阅读

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;


const int maxn = 10000005;
int vis[maxn];
int n;
//int eratosthenes()
//{
//    memset(vis,0,sizeof(vis));
//    for(int i=2;i<=n;i++)
//    {
//        for(int j=i*2;j<=n;j+=i)
//            vis[j]=1;
//    }
//}
int eratosthenes()///当算到10000000时快大概4秒的时间。此方法大概一秒能算出所有素数。
{
    memset(vis,0,sizeof(vis));
    for(int i=2;i<=(int)(sqrt(n)+0.5);i++)
    {
        if(!vis[i])
        for(int j=i*i;j<=n;j+=i)
            vis[j]=1;
    }
}


int main()
{
    scanf("%d",&n);
    eratosthenes();
    int cnt=0;
    for(int i=2;i<=n;i++)
    {
        if(!vis[i])
        {
            cnt++;
//            printf("%d ",i);
        }
    }
    printf("\nthe number :%d\n",cnt);
    return 0;
}


联系
我们