読者です 読者をやめる 読者になる 読者になる

メモリにやさしいエラトステネス

これで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 ");
	}
}