20191016特別テーマ:質量数

一覧:
判定+ふるい法
ふるい法:
エルボふるい法:
時間複雑度(O(n l o g n)O(nlogn)O(nlogn))テンプレート:

int s[N],num;
bool ex[N];

void prepare(){
	ex[1]=1;
	for(int i=1;i<=n;i++){
		if(ex[i])	continue;
		s[++num]=i;
		for(int j=2;i*j<=n;j++)
			ex[i*j]=1;
	}
}

線形ふるい:
時間複雑度(O(n)O(n)O(n))テンプレート:

int s[N],num;
bool ex[N];

void prepare(){
	ex[1]=1;
	for(int i==1;i<=n;i++){
		if(ex[i])	continue;
		s[++num]=i;
		for(int j=2;j<=num&&i*s[j]<=n;j++){
			ex[i*s[j]]=1;
			if(!(i%s[j]))	continue;
		}
	}
}

判断:
一般:
時間複雑度:(O(n)O(sqrt n)O(n))

bool pd(int s){
	for(int i=2;i<=sqrt(s);i++)
		if(!(s%i))	return false;
	return true;
}

miller_rabinrabin:
時間複雑度:(O(m l o g n)O(mlogn)O(mlogn))誤り確率:(4−s 4^{−s}4−s)注:2,3,5,7,11,13,17,19 2,3,5,7,11,17,17,19 2,19,19,19,2,3,5,7,11,13,17,19,19,3,5,7,11,13,17,19を選択して判断基数を行い,1 0,15 10^{15}1015内で正確性を保証する.テンプレート:

int ran[8]={0,2,3,5,7,11,13,17};

int quick(int p,int n,int mod){
	int r=1;
	p=p%mod;
	while(n){
		if(n&1)	r=r*p%mod;
		p=p*p%mod;
		n>>=1;
	}
	return r;
}

bool wit(int c,int s){
	int t=s-1,j=0;
	while(t%2==0){
		t/=2;
		j++;
	}
	int k=quick(c,t,s);
	if(k==1||k==s-1)	return true;
	while(j--){
		k=k*k%s;
		if(k==s-1)	return true;
	}
	return false;
}

bool m_r(int s){
	if(s==1)	return false;
	for(int i=1;i<=7;i++)
		if(s==ran[i])	return true;
	for(int i=1;i<=7;i++)
		if(s%ran[i]==0)	return false;
	for(int i=1;i<=7;i++)
		if(!wit(ran[i],s))	return false;
	return true;
}