质数

bool is_prime(int n){
	if(N<2)return false;
	rep(i,2,sqrt(n)){
		if(n%i==0)return false;
	}
	return true;
}

void primes(int n){
	CLR(v);
	rep(i,2,n){
		if(v[i])continue;
		for(int j=i;j<=n/i;j++)
			if(!v[i*j])v[i*j]=1;
	}
}

1. 依次考虑2~N之间的每个数i
2. 若v[i]=i,说明i是质数，保存它
3. 扫描不大于v[i]的每个质数p，令v[i*p]=p,也就是在i的基础上累积一个质因子p。因为p<=v[i],所以p就是合数i*p的最小质因子

int v[MAXN],prime[MAXN];
void primes(int n){
	CLR(v);
	m=0;
	rep(i,2,n){
		if(v[i]==0){
			v[i]=i;
			prime[++m]=i;
		}
		for(int j=1;j<=m; j++){
			//i有比prime[j]更小的质因子或者超出n的范围，停止循环
			if(prime[j]>v[i]||prime[j]>n/i)break;
			v[i*prime[j]]=prime[j];//prime[j]是合数i*prime[j]的最小质因子 
		}
	}
}

• 结合质数判定的试除法以及Eratisthenes筛法

• void divide(int n){
  	m=0;
  	rep(i,2,sqrt(n)){
  		if(n%i==0){
  			p[++m]=i,c[m]=0;
  			while(n%i==0)n/=i,c[m]++;
  		}
  	}
  	if(n>1){
  		p[++m]=n,c[m]=1;
  	}
  } 
  

• Pollard’s Rho（有空查阅）