これで1億までの素数も安心だね!!
intの32bitに情報を詰め込む作戦。
#include <cstdio> #include <cstring> #define N 100000000 #define mod_32(n) (n&((1<<5)-1)) int prime[(N>>5)+1]; void init(){ memset(prime,-1,sizeof(prime)); prime[0] &= ~(1<<0) & ~(1<<1); for(int i=2;i*i <= N;i++){ if( prime[i>>5] & (1 << mod_32(i)) ){ for(int j=i*i;j<=N;j+=i){ prime[j>>5] &= ~(1<<mod_32(j)); } } } } bool isprime(int n){ return !!(prime[n>>5] & (1<<mod_32(n))); } int main(){ int n; init(); while(~scanf("%d",&n)){ printf("%d is%sprime.\n",n,isprime(n)?" ":" not "); } }