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 1000001using 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;}