这个题艾式筛法及其位优化,就是用每一位储存储存是不是素数,然后把素数存在一个数组里利用。

这里他(i/2)/16是直接略去了2*n这些数,第i位表示2*i+1

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef unsigned int ui;
const int N=100000007;
int vis[N/32+50];
unsigned int sum[5800000];
int ans[5800000],tot=0;
 
void Prime (){
    ans[0]=sum[0]=2;
    tot=1;
    for (int i=3;i<N;i+=2)
        if (!(vis[i/32] & (1 << ((i/2)%16)))){
            ans[tot]=i;
            sum[tot]=sum[tot-1]*i;
            tot++;
            for (int j=3*i;j<N;j+=2*i)
                vis[j/32] |= (1 << ((j/2)%16));
        }
}
 
ui deal(int n){
    int p=upper_bound(ans,ans+tot,n)-ans-1;
    ui bns=sum[p];
    for(int i=0;ans[i]*ans[i]<=n;i++){
        ui t=ans[i];
        while(t*ans[i]<=n&&(t*ans[i]%ans[i]==0))
            t*=ans[i];
        if(t>1) bns*=t/ans[i];
    }
    return bns;
}
 
int main(){
    Prime();
    int t,cas=1,n;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        printf ("Case %d: %u\n",cas++,deal(n));
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注