三种素数筛的比较
在自然数集中，质数的数量不多而且分布比较稀疏，对于一个整数N，不超过N的质数大概有N/lnN个，即每lnN个数中可能会有一个质数。
在筛选0—N中的素数的方法较多:
1.试除法
bool is_prime(int n)
{
for(int i=2;i<=sqrt(n);i++)
if(n%i==0)return false;
return true;
}2.Eratosthenes筛选法
想法是：任意整数x的倍数 2x，3x，..都不会是质数
我们从2开始扫，从小到大扫每个数x,把他的倍数2x,3x,...,[N/x]*x标记为合数.
扫到一个数时，它不被2—x-1之间任何数整除,该数即为质数
当然，我们会发现，2和3都会把6标记为合数。
由此我们可知，小于x^2的x的倍数在扫更小的数时已经被扫了一遍。
就不必像2和3都会把6扫一遍那样多余的白白浪费运算时间了。
我们要做的就是对这个算法进行优化
：对于每个数x，我们只需从x^2开始扫，把x^2,(x+1)*x,...,[N.x]*x标记合数即可。
void primes(int n)
{
memset(v,0,sizeof(v));//标记合数
for(int i=2;i<=n;i++)
{
if(v[i])continue;
else cout<<i<<endl;//看是不是质数，是质数的话输出
for(int j=i;j<=n/i;j++)v[i*j]=1;
}
}当然这篇blog到此不会截止，我想说的是：虽然.Eratosthenes筛选法是让素数x从x^2往上开始2筛的，但还是会造成重复筛选。
就像2和3都会把6标记为合数一样，
虽然Eratosthenes筛选法是把x^2,(x+1)*x,...,[N.x]*x标记合数
但还是会造成重复筛选。
如：12=6*2,12=4*3，很明显12被重复筛选了，
Eratosthenes筛选法 的本质和爆破的试除法 一样，只不过减少了重复筛选的次数。
而我们想知道的是产生一个合数的唯一方式。
这时我们讲一下线性筛：
举个简单的例子：我们通过 从小到大累积质因子 来标记每个合数，让12=3*2*2是合数组成的唯一的方式
线性筛是通过 从小到大累积质因子 来标记每个合数，当我们理解这句话的含义时，实现代码就不难了
int v[maxn],prime[maxn];//prime用来记载质数
void primes(int n)
{
memset(v,0,sizeof(v));
m=0;//最小质因子
for(int i=2;i<=n;i++)
{
if(v[i]==0)
{ v[i]=i;prime[++m]=i; }//i是质数的话
//让当前数i乘上一个质因子
for( int j=1;j<=m;j++)
{
//i有比prime[j]更小的质因子 或超出n的范围停止
if(prime[j]>v[i] ||prime[j]>n/i )break;
//prime[j]是合数i*prime[j]的最小质因子
v[i*prime[j]]=prime[j];
}
}
for(int i=1;i<=m;i++)cout<<prime[i]<<endl;
}这种方法省时就省时在，不会造成重复筛选！
其实关于质数的题目还有一个应用就是：质因数分解
pi序列都为质数，ci为次幂
对任何N，都有：
N=p1^c1*p2^c2.......
由此可以利用 试除法 和 Eratosthenes筛选法 完成质因数分解：
其实 它的一个更好的应用是求最大质因子 因为一个数字不可能有两个大于根号的因子，还是素因子所以我们函数内，for循环的条件是：
for(int i=2;i<=sqrt(n);i++)
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
const int maxn=1e5;
long long p[maxn];
long long c[maxn];
void divide(int n)
{
int m=0;
for(int i=2;i<=sqrt(n);i++)
{
if(n%i==0)//i为质数
{
p[++m]=i;c[m]=0;
while(n%i==0)
{
n/=i;c[m]++;
}
}
} //最后剩余的数不能为任何区间内质数整除,则剩余的数 也为质数
if(n>1)
{p[++m]=n;c[m]=1; }
for(int i=1;i<=m;i++)
cout<<p[i]<<" "<<c[i]<<endl;
}
int main()
{
int n;cin>>n;
divide(n);
return 0;
}