题解 P3912 【素数个数】

_zby_ · 2019-02-21 18:36:48 · 题解

本题解主要对 @不到前10不改名 的题解进行补充说明

先看下普通筛法代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#include<iomanip>
#include<stack>
#include<sstream>
#include<string> 
typedef long long LL;
typedef double db;
using namespace std;
template<typename T>void read(T &x) {
    char ch=getchar(); x=0; T f=1;
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') f=-1,ch=getchar();
    for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
}
bool a[100000005];
int main(){
    int n,ans=0;
    read(n);
    for(int i=2;i<=n;i++){
        if(!a[i]){
            ans++;
            for(int j=i+i;j<=n;j+=i)
            a[j]=1;
        }
    }
    cout<<ans;
    return 0;
}

当然是 两个点TLE 了

这种方法缺点在哪？

题目只要求求出素数个数，你却多此一举把素数都找了出来！！

我们知道 所有数都分为合数和质数还有1三种

所以其实只要我们 把合数的个数找出来 就完成了任务

就像 @不到前10不改名 的代码一样

#include<stdio.h>
bool a[100000000];//话说我当初short int都没过，只从80到了90
int main()
{
    int n,i,j,s=0;
    scanf("%d",&n);
    s=n-1;//把一给去掉
    for(i=2;i*i<=n;i++)
    {if(a[i]==0)//正常筛法，无需解释（无黑科技，也不用高级筛法）
    for(j=i*2;j<=n;j+=i)//结合正常判断素数去做就能达到高级筛法的效果
    if(a[j]==0)（例如说i*i和筛法结合可以节省不少时间）
    {a[j]=1;
    s--;}}
    printf("%d",s);
    return 0;
}

这个代码有一个优化很多人不理解

就是第一个for循环处的 i*i<=n

也就是 i<=sqrt(n)

其实，比sqrt(n)还大的合数是有的

但是 这些合数都是sqrt(n)之前的质数或合数的倍数！！

在程序运行到

for(j=i*2;j<=n;j+=i)//结合正常判断素数去做就能达到高级筛法的效果
    if(a[j]==0)（例如说i*i和筛法结合可以节省不少时间）
    {a[j]=1;
    s--;}}

的时候就 已经被标记过了！！

这下子，这个代码你懂了吗？