素数（质数）判断、打印素数表（Eratosthenes筛法）、质因子分解————附完整代码

1 概念

素数：除1和它本身之外，不能被其他数整数的一类数。

即对于一给定的正整数n，如果对任意的正整数(1<a<n)，都有n%a!= 0成立，那么称n是素数；否则如果存在a(1<a<n),使得n%a ==0，那么称n是合数。

1既不是素数，也不是合数。

2 素数的判断

2.1 思想

由素数的定义可知，一个整数要被判断为素数，需要判断n是否能被2, 3,…,n-1中的一个整除，如果没有，则是素数，否则则不是。这样判断的时间复杂度为O(n)，不是很理想。

由于2～n中存在的约数，不妨设为k，即n%k==0，那么
$k*(n/k）== n$k∗(n/k）==n可知，n/k也是n的一个约数，且k与n/k一定满足其中一个小于sqrt（n), 另一个大于sqrt（n）；

这启发我们只需要判断n能否被$2，3，。。\left \lfloor \sqrt{N}\right \rfloor$2，3，。。⌊N​⌋中的一个整除,即可判定n是否为素数。时间复杂度为O(sqrt(n))。

2.2 实现代码

bool isPrime(int n){
    if(n <= 1) return false;//特判
    int sqr = (int)sqrt(1.0 * n);
    for (int i = 2; i <= sqr; ++i)//遍历2到根号n
    {
        if(n % i == 0) return false;//如果n是i的倍数，则不是素数
    }
    return true;
}

• 由于sqrt的参数要求是浮点数，因此需要乘以1.0来类型转换

3 素数表的获取

3.1 朴素算法

3.1.1 思想

打印1～n范围内素数表的方法，从1～n进行枚举，判断每个数是否是素数，如果是素数，加入素数表。枚举的时间复杂度为$O(n)$O(n),判断素数的时间复杂度为$O(\sqrt{n})$O(n​),因此总时间复杂度为$O(n\sqrt{n})$O(nn​),这对于n不超过10⁵的大小是没有问题的。

3.1.2 3 实现代码

打印100范围内的素数：

const int MAXN = 101;//表长
int prime[MAXN], pNum = 0;//存放素数和素数个素
bool p[MAXN] = {0};//p[i]==true，表示是素数
void Find_Prime(){
    for (int i = 1; i < MAXN; ++i)//不能写成i <= MAXN
    {
        if(isPrime(i) == true){//存入prime数组
            prime[pNum++] = i;
            p[i] = true;
        }
    }
}

完整代码：

#include <cstdio>
#include <cmath>

const int MAXN = 101;//表长
int prime[MAXN], pNum = 0;//存放素数和素数个素
bool p[MAXN] = {0};//p[i]==true，表示是素数

bool isPrime(int n){
    if(n <= 1) return false;//特判
    int sqr = (int)sqrt(1.0 * n);
    for (int i = 2; i <= sqr; ++i)//遍历2到根号n
    {
        if(n % i == 0) return false;//如果n是i的倍数，则不是素数
    }
    return true;
}


void Find_Prime(){
    for (int i = 1; i < MAXN; ++i)//不能写成i <= MAXN
    {
        if(isPrime(i) == true){//存入prime数组
            prime[pNum++] = i;
            p[i] = true;
        }
    }
}

int main(int argc, char const *argv[])
{
    Find_Prime();//打印素数表
    for (int i = 0; i < pNum; ++i)
    {
        printf("%d", prime[i]);
        if(i < pNum - 1){
            printf(" ");
        }
    }
    return 0;
}

3.2 Eratosthenes筛法

3.2.1 思想

算法从小到大枚举所有的数，对于每个素数，筛去它的所有倍数，剩下的就都是素数了。
如果一个数a没有被前面的数筛去，那么a一定是素数，因为如果a不是素数，那么a一定有小于a的素因子，这样在之前的步骤中，a就一定不会筛掉。
算法的时间复杂度为：$O(\sum_{i=1}^{n/i})=O(nloglogn)$O(∑i=1n/i​)=O(nloglogn)

例如，求1～15中的所有素数：

3.2.2 实现代码

int Prime[MAXN], pNum = 0;
int p[MAXN];//是素数，p[i]为false
void Find_Prime(){
    for (int i = 2; i < MAXN; ++i)
    {
        if(p[i] == false){//如果i是素数
            prime[pNum++] = i;
            for (int j = i + i; j < MAXN; j += i)//注意不能写成i<=maxn
            {
                //筛去所有i的倍数
                p[j] = true;
            }
        }
    }       
}

求解100以内的所有素数：

#include <cstdio>
//#include <cstring>

const int MAXN = 101;
int prime[MAXN], pNum = 0;
bool p[MAXN] = {0};

void Find_Prime(){
    for (int i = 2; i < MAXN; ++i)
    {
        if(p[i] == false){
            prime[pNum++] = i;
            for (int j = i + i; j < MAXN; j += i)
            {
                p[j] = true;
            }
        }
    }
}

int main(int argc, char const *argv[])
{
//    memset(p, 0, sizeof(p));

    Find_Prime();
    for (int i = 0; i < pNum; ++i)
    {
        if(i != 0) printf(" ");
        printf("%d", prime[i]);
    }
    return 0;
}

小结：

• 1不是素数；
• 素数表长至少比b大1；
• 在Find_Prime函数中，要特别留意i<maxn,不能写成i<=maxn;
• 在main函数中记得调用Find_Prime()，不然不会得到结果。

4 质因子分解

4.1 思路

质因子分解：将一个整数n写成一个或多个质数的乘积形式。

如：
$6 = 2\times3,8=2\times2\times2,180=2\times2\times3\times3\times5$6=2×3,8=2×2×2,180=2×2×3×3×5，或者写成指数的形式，$6=2^{1}\times3^{1},8=2^{3},180=2^{2}\times3^{2}\times5^{1}$6=21×31,8=23,180=22×32×51。

注意：1本身不是素数，没有质因子。

下面正对大于1的正整数计算质因子：

由于每个质因子都可以不止出现一次，因此定义一个结构体factor，来存放质因子及其个数：

struct factor{
	int x;//质因子
	int cnt;//其个数
}fac[10];

考虑到$2\times3\times5\times7\times11\times13\times17\times19\times23\times29$2×3×5×7×11×13×17×19×23×29就已经超过int范围，因此对于一个int型范围的数来说，fac数组只需开到10就可以。

对于180来说：
fac[0].x = 2;
fac[0].cnt = 2;
fac[1].x = 3;
fac[1].cnt = 2;
fac[2].x = 5;
fac[2].cnt = 1;

之前的提到，对于一个整数n来说，如果它存在1和它本身以外的因子，那么一定是在sqrt(n)左右成对出现。

现在把这个用在分解质因子上，得到一个结论：
对于一个整数n，如果它存在[2,n]范围内的质因子，要么这些质因子全部小于等于sqrt(n),要么只存在一个大于sqrt(n)的质因子，其余的质因子小于等于sqrt(n)。

现，得到解题模版：

• 1 枚举1～sqrt(n)范围内的所有质因子p，判断p是否是n的因子。
  • 如果p是n的因子，那么给fac数组中增加质因子p，并初始化其个数为0.然后，只要p还是n的因子，就让n不断除以p，每次操作令p的个数加1，直到p不再是n的因子；
  • 如果p不是n的因子，那直接跳过；
• 2 如果在上面步骤结束后n仍然大于1，有且仅有一个大于sqrt(n)的质因子（有可能是n本身），这是需要把这个质因子加入fac数组，并令其个数为1。
• 至此，fac数组中存放的就是质因子分解的结果，时间复杂度为$O(\sqrt{n})$O(n​)。

4.2 实现代码

//n为计算的数，num为n的质因子个数，初值值为0
void calPrimeFactor(int n, int &num){
    // int num = 0;
    int sqr = (int)sqrt(1.0*n);
    //在素数表内以及素数的值小于等于根号n内进行统计
    for (int i = 0; i <= MAXN && prime[i] <= sqr; ++i)
    {
        if(n % prime[i] == 0){//如果prime[i]是n的质因子
            fac[num].x = prime[i];
            fac[num].cnt = 0;
            while(n % prime[i] == 0){//计算出prime[i]的个数
                fac[num].cnt++;
                n /= prime[i];
            }
            num++;//不同质因子个数加1
        }
    }
    //如果无法被根号n以内的质数除尽
    if(n != 1){
        fac[num].x = n;//那么一定存在大于根号n的质因子
        fac[num++].cnt = 1;
    }
}

完整示例为：

#include <cstdio>
#include <cmath>

struct factor
{
    int x;
    int cnt;
}fac[10];

const int MAXN = 30;//从2开始连乘素数到29就超过int的范围
int prime[MAXN], pNum = 0;
bool p[MAXN] = {false};

void find_Prime(){//打印素数表
    for (int i = 2; i < MAXN; ++i)
    {
        if(p[i] == false){
            prime[pNum++] = i;
            for (int j = i + i; j < MAXN; j +=i)
            {
                p[j] = true;
            }
        }
    }
}

//n为计算的数，num为n的质因子个数，初值值为0
void calPrimeFactor(int n, int &num){
    // int num = 0;
    int sqr = (int)sqrt(1.0*n);
    //在素数表内以及素数的值小于等于根号n内进行统计
    for (int i = 0; i < pNum && prime[i] <= sqr; ++i)
    {
        if(n % prime[i] == 0){//如果prime[i]是n的质因子
            fac[num].x = prime[i];
            fac[num].cnt = 0;
            while(n % prime[i] == 0){//计算出prime[i]的个数
                fac[num].cnt++;
                n /= prime[i];
            }
            num++;//不同质因子个数加1
        }
    }
    //如果无法被根号n以内的质数除尽
    if(n != 1){
        fac[num].x = n;//那么一定存在大于根号n的质因子
        fac[num++].cnt = 1;
    }
}

int main(int argc, char const *argv[])
{
    find_Prime();
    int n = 180;
    int num = 0;
    calPrimeFactor(n,  num);
    for (int i = 0; i < num; ++i)
    {
        printf("%d %d\n", fac[i].x, fac[i].cnt);
    }
    return 0;
}

4.3 扩展

最后，指出要求一个正整数N的因子个数，只需要对其质因子分子，得到各质因子p_i的个数分别是e₁、e₂、…、e_k,于是N的因子个数就是(e₁+1)*(e₂+2)*…*(e_k+1)。
原因是，对每个质因子p_i都可以选择其出现0次、1次、…、e_i次，共有e_i+1次中可能，组合自来就是答案。

N的所有因子之和为$(1+p_{1}+p_{1}^{2}+...+p_{1}^{e_{1}})*(1+p_{2}+p_{2}^{2}+...+p_{2}^{2})*....*(1+p_{k}+p_{k}^{2}+...+p_{k}^{e_{k}})=\frac{1-p_{1}^{e_{1}+1}}{1-p_{1}}*\frac{1-p_{1}^{e_{2}+1}}{1-p_{2}}*...*\frac{1-p_{k}^{e_{1}+1}}{1-p_{k}}$(1+p1​+p12​+...+p1e1​​)∗(1+p2​+p22​+...+p22​)∗....∗(1+pk​+pk2​+...+pkek​​)=1−p1​1−p1e1​+1​​∗1−p2​1−p1e2​+1​​∗...∗1−pk​1−pke1​+1​​。