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