嘉泽 P2120: 【基础】半质数题解

简要题意：

求区间内能分解为两个质数乘积的数。

欧拉筛先筛素数。

然后再筛答案。

时间复杂度： \(O(n)\).

实际得分：\(100pts\).

#pragma GCC optimize(2)

#include<bits/stdc++.h>

using namespace std;

const int N=5e6+1;

inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}

    int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}

bool h[N]; int s,e;

int prime[N],cnt=0;

bool hal[N];

inline void Euler() {

    h[1]=1;

    for(int i=2;i<N;i++) {

        if(!h[i]) prime[++cnt]=i;

        for(int j=1;j<=cnt && i*prime[j]<N;j++) {

            h[i*prime[j]]=1;

            if(i%prime[j]==0) break;

        }

    } //for(int i=1;i<=cnt;i++) printf("%d ",prime[i]);

    // 欧拉筛

    for(int i=1;i<=cnt;i++) {

//      printf("%d %d\n",i,prime[i]);

        if(prime[i]*prime[i]>=N) break;

        for(int j=i;j<=cnt;j++) {

//          printf("%d %d %d\n",j,prime[j],prime[i]*prime[j]);

            if(prime[i]*prime[j]>=N) break;

            hal[prime[i]*prime[j]]=1;

        }

    } //筛半质数

}

int main(){

    Euler(); s=read(),e=read();

    int sum=0; for(int i=s;i<=e;i++) sum+=hal[i];

    printf("%d\n",sum);

    return 0;

}

/**************************************************************

    Problem: 2120

    User: bfw

    Language: C++

    Result: 正确

    Time:42 ms

    Memory:31320 kb

****************************************************************/

巴特西

嘉泽 P2120: 【基础】半质数题解

最新文章

热门文章

巴特西

嘉泽 P2120: 【基础】半质数 题解

最新文章

热门文章

嘉泽 P2120: 【基础】半质数题解