素数

1、素数

（1）暴力求解法

根据素数的概念，没有1和其本身没有其他正因数的数。

所以只需枚举比这个数小的数，看能整除即可；

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

bool determine(int number)
{
if(n<=2)return false;
if(!n%2)return false;
    for(int i=3;i<=ceil(sqrt(number));i+=2)
//去掉了偶数的判断，效率提高一倍
    /*如果number整除以i，那么会得到两个的因数，
    而较小的那个因数不会超过number的二分之一次方；
    所以只需判断到number的平方根向上取整即可； */
        if(number%i);
        else return false;
    return true;
}
int main()
{
    int sum;
    cin>>sum;
    if(determine(sum))
        cout<<"YES!";
    else cout<<"NO!";
    return 0;
}

时间复杂度：o(sqrt(n)/2);

空间复杂度：几乎没有；

（2）一般线性筛法：

因为任何一个合数都能分解成几个素数相乘的形式；

所以可以做一个表，首先把2设为质数，然后将2的倍数设为合数，剩下的数就是新得到的质数，然后重复这个过程，直到筛到合适的范围即可；

但是这个算法有缺陷：

1、同一个数可能被筛多次，这就产生了多余的步骤。

2、占用空间很大，如果使用bool数组的话，只能筛到1e9；

3、从1-n筛，不能从m-n开始筛；

#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;

bool s[1000000000];
int m,n;

int main()
{
    cin>>m>>n;
    memset(s,true,n);
    s[0]=s[1]=0;
    //输出M—N之间所有素数；
    for(int i=2;i<=ceil(sqrt(n));++i)
        if(s[i])
        {
            for(int j=i;j<=n;++j)
                if(s[i*j])
                    s[i*j]=false;
        }
    for(int i=m;i<=n;++i)
        if(s[i])
            cout<<i<<' '; 
    return 0;
}

时间复杂度：o(n*loglogn);

空间复杂度：很大！注意数据大的话可能会爆空间；

（3）线性筛法求素数

这个占空间就更大了，需要使用一个bool数组和int数组

而亲身试验得到int数组最多开到1e8……

很无语，快确实是快了，但是测试数据一大，爆空间就更容易了；

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

int m,n,sum;
bool inp[1000000000];
int s[100000000]={0,0};

int main()
{
    cin>>m>>n;
    for(int i=2;i<=n;++i)
    {
        if(!inp[i])
            s[sum++]=i;
        for(int j=0;j<sum&&i*s[j]<=n;++j)
        {
            inp[i*s[j]]=true;
            if(!(i*s[j]))
                break;
        }
    }
    for(int i=m;i<=n;++i)
        if(!inp[i])
            cout<<i<<' ';
    return 0;
}

2、唯一分解定理

任何数都可以被唯一的分解成多个素数之积

例如：456=2*2*2*3*19；

#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstdlib>
using namespace std;

bool s[1000000];
int m,n,sum=0,num;
int Prime[1212121];
int zhi[1500];

void Primes()
{
    for(int i=1;i<=num;++i)
        s[i]=true;
    s[0]=s[1]=0;
    for(int i=2;i<=num;++i)
        if(s[i])
        {
            Prime[++sum]=i;
            for(int j=i;j<=num;++j)
                if(s[i*j])
                    s[i*j]=false;
        }
}

int main()
{
    int flag=0;
    cin>>num;
    int number=num;
    Primes();
    if(s[num])
    {
        cout<<num<<'='<<num;
        return 0;
    }
    cout<<num<<"=";str.chu();
    while(num>1)
    for(int i=1;num>1&&i<=sum;++i)
        if(!(num%Prime[i]))
        {
            zhi[++flag]=Prime[i];
            num/=Prime[i];
        }
    sort(zhi+1,zhi+flag+1);
    cout<<zhi[1];
    for(int i=2;i<=flag;++i)
        cout<<"*"<<zhi[i];
    return 0;
}
首先做一个质数表，并把质数存到数组里，然后用数模每个素数，如果为0则记录素数，最后排个序输出；