质数和合数

在这个内容中，我们将学习质数和合数的内容，有部分内容是我们小学的时候就已经学习过了，还有部分的知识就涉及到数论的内容中了

质数

在学习质数之前，我们要先知道一下质数的定义，什么样的数才算是一个质数？

质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数（规定1既不是质数也不是合数）

—来源于百度百科

判断质数

知道质数的定义后，我们就要知道如何才能够求解出一个数是不是质数，判断一个数是不是质数，那就看从2开始到小于它一位的数是否都不能将它整除

这样来看，这个程序还是很好写的

代码如下

bool isprime(int m)
{
    if(m<2) return false;
    for(int i = 2;i<m-1;i++)
    {
        if(m%i==0) return false;
    }
    return true;
}

这样的代码在求一个数是否是质数的时候是非常方便快捷的，但是在求解多个数是否是质数的话就不够优秀了，因为时间复杂度可能会超时

这时候就要对代码进行优化，以16这个数为例，16不可以被9，10，11，12，13，14，15这些数整除，这是显而易见的，进而我们将代码加快了一倍，但是还不够，我们知道4可以整除16，8也可以整除16，但是在2的时候，16就已经被判断为合数了，或者说，我们只要判断16的平方根次，4*4=16，那么我们就只要判断最多3次，就可以知道16是不是质数了，因为4后面的数都不会被16整除或者可以整除但是前面已经它(指4后面可以将16整除的数)的因数了

因此，我们的代码可以再简化一些

bool isprime(int m)
{
    if(m<2) return false;
    for(int i = 2;i<=m/i;i++)
    {
        if(m%i==0) return false;
    }
    return true;
}

这样，我们就可以在不超时的情况下判断多个数是不是质数了

分解质因数

在判断完一个数是否为质数后，我们现在想知道到底是多少个质数可以做到将一个数分解成多个数相乘的结果

举个例子, 36 = 4 9, 36是由1个4和1个9组成的, 4 = 2 2,9 = 3 3,所以这个式子又可以转换为36 = 2 2 3 3，即36是由2个2和2个3组成的，现在我们给出多个数相乘，我们要计算多个数相乘得到的数是由哪些数组成的，其实就是求每一个数的是由哪些数相乘的，最后叠加就可以了

代码如下

void prime(int m)
{
    for(int i = 2;i<=m/i;i++)
    {
        //找到一个可以整除的数了
        if(m%i==0)
        {
            int s = 0;
            //把这个数直接除完
            while(m%i==0)
            {
                m/=i;
                s++;
            }
            cout<<i<<' '<<s<<endl;
        }
    }
    //判断一下最后的数是多少,不是1的话就要单独再输出出来
    if(m>1) cout<<m<<' '<<1<<endl;
    cout<<endl;
}

筛质数

现在，我们的要求更加难度了，我们要求1~n里面的数有多少个质数，比如说1-1000000内有多少个质数，这样的话，如果用我们传统的求法（就是一开始说的那个）来求的话肯定会超时的，要计算的数实在是太多了，所以为了能够更加快速的求出一个范围里面的质数，这里有两种质数筛法，第一种是欧拉筛法，第二种是线性筛法，埃氏筛法比线性筛法要慢一些，但是它的思想是很重要的

埃氏筛法

首先将2到n范围内的整数写下来。其中2是最小的素数。将表中所有的2的倍数划去，表中剩下的最小的数字就是3，他不能被更小的数整除，所以3是素数，再将表中所有的3的倍数划去…… 以此类推，如果表中剩余的最小的数是m，那么m就是素数，然后将表中所有m的倍数划去，像这样反复操作，就能依次枚举n以内的素数

埃氏筛法的时间复杂度是0(n*log(logn))

代码如下

定义

#include <iostream>
#include <algorithm>
using namespace std;
const int N= 1000010;
int primes[N], cnt;
bool st[N];

函数

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (st[i]) continue;
        primes[cnt ++ ] = i;
        for (int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}

线性筛法(欧拉筛法)

线性筛法就是在埃氏筛法的基础上再次进行了优化，使得我们可以更加快速的判断质数了

开一个n+1大小的bool数组st[n]来存放每一个元素的筛留情况(即对于st[n]的每个数与下标号相同，对于任意st[n]有st[n]=0,st[n]=1两种情况，如果st[n]!=true则是素数，反之是合数)

再开一个数组prime[n]来存放筛出的素数以便最后输出结果

上述就是我们在使用线性筛法时的方式

对于一个数k,总是进行从n*prime[0]~n*prime[j]，直到if(n%prime[j]==0)成立时break掉

代码如下

定义

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1000010;
int prime[N],cnt;
bool st[N];

函数

void isprime(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) prime[cnt++] = i;
        for(int j = 0;prime[j]<=n/i;j++)
        {
            st[prime[j]*i] = true;
            if(i%prime[j]==0) break;
        }
    }
    cout<<cnt<<endl;
}

总结

以上就是质数的相关知识啦，如果你用心看到这里的话，相信你一定会有所收获的捏~(￣▽￣)~*

如果我写的有什么不明白的地方或者有歧义的地方还希望大家可以告诉我(QQ1594463152),谢谢捏~(￣▽￣)~*