一、素（质）数定义

定义：

质数（prime number）又称素数，有无限个。

质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。

此处一定要注意，1不是素数，在素数判定中，1不是素数。

以下对于十的N次方数，全部表示为1eN

二、素（质）数判定

1.根据素数的定义，我们可以直到素数的因子只能为1和他本身。所以我们可以根据这个思想:只要他不被从2到n-1之前的任何一个数整除（即没有除1和本身的其他因子）该数即为素数。

2.故第一种判断方法：时间复杂度O（n）

const int maxn=1e6+5;
const int INF=1e9;
int judge_prime(int n)
{
    if(n==1)
        return 0;//0代表不是素数，1不是素数。
    for(int i=2;i<=n-1;i++)
        if(n%i==0) return 0;
    return 1;//1代表是素数
}
int main()
{
    int n;
    scanf("%d",&n);
    int ans=judge_prime(n);
    printf("%s\n",ans==1?"YES":"NO");
    return 0;
}

3.但是我们可以看到，时间复杂度太高，1sec的极限是1e8次计算，如果要判断一个1e10+的数是不是素数，这样显然会超时。

所以我们应该改进一下算法，我们直到一个数可以表示为两个数的乘积，所以两个数应该分别在n^(1/2)之前与n^(1/2)之后，不可能同时在前或者在后（这个地方应该都懂，不举例了）。也就是说在n^(1/2)之前有因数，n^(1/2)之后必有因数。所以我们只需要判断n^(1/2)之前有没有因数就好，当然也可以判断n^(1/2)-n-1有没有因数。

所以程序的改进如下：时间复杂度O（n^(1/2)）

typedef long long ll;
const int maxn=1e6+5;
const int INF=1e9;
int judge_prime(ll n)
{
    if(n==1)
        return 0;//0代表不是素数，1不是素数。
    for(ll i=2;i<=sqrt(n);i++)//sqrt根号运算
        if(n%i==0) return 0;
    return 1;//1代表是素数
}
int main()
{
    ll n;
    scanf("%lld",&n);
    int ans=judge_prime(n);
    printf("%s\n",ans==1?"YES":"NO");
    return 0;
}

PS：因为该算法是为了计算大数写的，所以int->long long.

三、素数打表

1.用筛法求素数的基本思想是：把从1开始的、某一范围内的正整数从小到大顺序排列， 1不是素数，首先把它筛掉。剩下的数中选择最小的数是素数，然后去掉它的倍数。依次类推，直到筛子为空时结束。

2.首先如果我们要求输出1000之前的素数，上面所述的判定方法是可以的，即加入一个for(循环就可以）

    for(int i=1;i<=n;i++)
        if(judge_prime(i))
            printf("%d ",i);

但是时间是一个问题，时间复杂度：O（n^(3/2))  如果数据为1e6，则需要1e6*1e3次计算，所以还是需要优化。

3.既然题目要求输出，N之前的素数，我们是不是可以对齐做一下标记呢，到时只需要判断一下就好了。如果一个数是素数那么他的倍数绝对不是素数，就这样我们把他们事先标记一下即可。

时间复杂度 O（N)  N为1e6之前的素数个数，//大大优化了时间，大约为O（78499）

筛法复杂度 O（nlgn）只能筛到1e6～1e7

typedef long long ll;
const int maxn=1e6+5;
const int INF=1e9;
bool vis[maxn];//int vis[maxn]一个意思
int prime[maxn];//记录素数
ll cnt=0;//素数个数
void set_prime()
{
    for(int i=1;i<maxn;i++)
        vis[i]=(i==1?false:true);//假设除了1以外都是素数
    for(int i=2;i<maxn;i++)
        if(vis[i])
        {
            prime[++cnt]=i;//记录当前素数
            for(int j=2*i;j<maxn;j+=i)
                vis[j]=false;//i的倍数一定不是素数
        }
}
int main()
{
    set_prime();
    for(int i=1;i<=cnt&&prime[i]<1000000;i++)
        printf("%d ",prime[i]);
    return 0;
}

4.这样的素数筛，还有个缺陷，就是6=2*3=3*2,6被2筛过了，但他又被3筛了一遍。为了避免这种情况出现，我们可以用每个数最小的因子去筛他，比如我们让6被2筛，不被3筛，怎么做到呢。接下来一种筛法：

筛法时间复杂度 O（n） 所以这被称为线性筛。

typedef long long ll;
const int maxn=1e6+5;
const int INF=1e9;
bool vis[maxn];//int vis[maxn]一个意思
int prime[maxn];//记录素数
ll cnt=0;//素数个数
void set_prime()
{
    for(int i=1;i<maxn;i++)
        vis[i]=(i==1?false:true);//假设除了1以外都是素数
    for(int i=2;i<maxn;i++)
    {
        if(vis[i]) prime[++cnt]=i;
        for(int j=1;j<=cnt&&i*prime[j]<maxn;j++)
        {
            vis[i*prime[j]]=false;
            if(i%prime[j]==0) break;//保证被筛的是他最小的质因子
        }
    }
}
int main()
{
    set_prime();
    for(int i=1;i<=cnt&&prime[i]<1000000;i++)
        printf("%d ",prime[i]);
    return 0;
}

四、欧拉函数

1.欧拉函数是小于n的正整数中与n互质的数的数目（φ(1)=1）。此函数以其首名研究者欧拉命名(Euler's totient function)，它又称为Euler's totient function、φ函数、欧拉商数等。

通式： 

由通式我们不难看出，欧拉函数的值止于该数能分解的质因数的种类有关。

2.

欧拉函数是积性函数——若m,n互质，

特殊性质：当n为质数时，

  , 证明与上述类似。

若n为质数则 

当不互质时，即m%n==0，n的因子，m全部都有，所以oula（m*n)=oula(m)*n

3.下面我们按照欧拉筛法，将欧拉函数补充完：

void set_prime()
{
    for(int i=1;i<maxn;i++)
        vis[i]=(i==1?false:true);//假设除了1以外都是素数
    for(int i=2;i<maxn;i++)
    {
        if(vis[i]) prime[++cnt]=i,oula[i]=i-1;
        for(int j=1;j<=cnt&&i*prime[j]<maxn;j++)
        {
            vis[i*prime[j]]=false;
            if(i%prime[j]==0)
            {
                oula[i*prime[j]]=oula[i]*prime[j];//当他们不互质时，有共同因子    
                break;
            }
            oula[i*prime[j]]=oula[i]*oula[prime[j]];//互质时积性函数分解
        }
    }
}

4.费马小定理的延伸：当p为质数时，同余方程 N^x=1(mod p)（等于号为同于号，不是等于号），该方程的解为oula（p）-1.

                                   谢谢阅读！喜欢点赞！