hdu3826 素数罗选

hdu3826 素数筛选

解题思路：保存10^6前的素数再逐个判断

没把“lld”改为“I64d”  wa   了一个下午。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

//============================================================================
// Name        : hdu3826__.cpp
// Author      : ssslpk
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include<cstdio>
#include<cmath>
#include<cstring>

#define int64 long long
#define N 1000001

using namespace std;

int g[N]={0};
int plen,pri[N]={0};

void Prime()
{
    int i,j;
    plen=0;
    for(i=2;i<N;i++)
    {
        if(!g[i])
        {
            pri[plen++]=i;
            for(j=2;i*j<N;++j)
                g[i*j]=1;
        }
    }
}
bool check(int64 n)
{
    for(int i=0;i<plen &&pri[i]<n;i++)
    {
        if(n%pri[i]==0)
        {
             n=n/pri[i];
            if(n%pri[i]==0)return false;
        }
    }
    return true;
}
int main() {
    Prime();
    int cas;
    scanf("%d",&cas);
    for(int k=1;k<=cas;k++)
    {
        int64 n;
        scanf("%I64d",&n);
        printf("Case %d: ",k);
        if(check(n))
        {
            int64 tmp=(int64)sqrt(n*1.0);
            if(tmp*tmp == n)printf("No\n");
            else
            printf("Yes\n");
        }
        else printf("No\n");
    }
    return 0;
}