第一课时

复习及引入

质数判断

bool isPrime(int x){
    if(x<2) return false;
    for(int i=2;i*i<=x;i++){
        if(x%i==0) return false;
    }
    return true;
}

复杂度分析 O(n)O(\sqrt{n})

引入问题,输入n(1n1061\leq n\leq10^6)个数字(0x1060\leq x \leq 10^6),判断每个数是不是质数?

利用已有知识,程序框架:

while(n--){//循环n次
    cin>>x;//输入数字
    if(isPrime(x)){//判断x是否是质数
        cout<<"Yes\n";
    }else{
        cout<<"No\n";
    }
}

我们来分析下时间复杂度 O(nx)O(n\sqrt{x})

思考,当前数据范围下是否能在1s时限内求出答案。

回答:106×103=10910^6\times 10^3 = 10^9 会超时。

进一步,该怎么去更快的处理大范围内的质数?

我们提前设置一个标记数组prime[N] ,提前标记好数字的质数状态,这样就能减少重复判断。

引出质数筛法

核心思想:唯一分解定理

每个大于1的自然数,要么本身就是质数,要么可以写为2个或以上的质数的积,而且这些质因子按大小排列之后,写法仅有一种方式。

埃氏筛

​ 埃拉托斯特尼选筛法,简称埃氏筛。要得到自然数n以内的全部素数,必须把不大于根号n的所有素数的倍数剔除,剩下的就是素数。

来理解下埃氏筛的思想

根据唯一分解定理的前半截“每个大于1的自然数,要么本身就是质数,要么可以写为2个或以上的质数的积”,那么换个角度去理解,合数一定是某个质数的倍数

  • 6=2×36=2\times 3
  • 12=2×2×312=2\times 2\times 3
  • 15=3×515=3\times 5

那么,当我确定一个数为质数,我自然可以将它所有的范围内的倍数(2\ge 2)找出来,这些倍数一定是合数。

也就是若pp为质数,那么j×p,(j2,j×pn)j\times p,(j\ge2,j\times p\le n ) 就是合数。

以30以内的筛选为例

配合图片,尝试手动模拟筛选过程。

算法步骤:

  1. 设置一个标记数组vis[N],初始化为0。0-是质数 1-不是质数
  2. 处理特殊值 0 ,1
  3. 从2开始,依次将范围内的质数的倍数标记为1(非质数)

初版:

const int N=1e6+5;
bool vis[N];
void esieve(int n){//标记0~n的数字的质数状态,并统计质数个数
	vis[0]=vis[1]=1;//0,1属于非质数
	for(int i=2;i<=n;i++){//标记剩下的2~n的数字的状态
		if(vis[i]==0){//判断i是不是质数 思考:为什么这样就能判断i是质数?
			for(int j=2*i;j<=n;j+=i){//遍历范围内的i的倍数
				vis[j]=1;//将倍数标记为1(非质数)
			}
		}
	}
}

思考:第6行,为什么这样就能判断i是质数?

解答:状态数组初始化为0,循环的方向是从小到大,过程中质数的在范围内的倍数都会被筛选掉。那么到i如果还是0,意味着质因子中不包含前面的这些质数,一个数在2~i-1这个范围内没有因子,那么他就是质数。

优化1

根据约数的分布性,一个数n如果是合数,其中较小的约数范围一定是在n\sqrt{n} 内。那么对于n+1n\sqrt{n}+1 \sim n 范围内的合数,一定可以被2n2 \sim \sqrt{n} 内的质数筛选掉。

const int N=1e6+5;
bool vis[N];
void esieve(int n){//标记0~n的数字的质数状态,并统计质数个数
    vis[0]=vis[1]=1;
	for(int i=2;i*i<=n;i++){//标记剩下的2~n的数字的状态 优化:到根号n即可停止
		if(vis[i]==0){//判断i是不是质数 
			for(int j=2*i;j<=n;j+=i){//遍历范围内的i的倍数
				vis[j]=1;//将倍数标记为1(非质数)
			}
		}
	}
}

优化2

过程中可发现很多数字被重复筛选了。

接下来就是减少重复筛选,以提高运行速度。

观察重复的数字 :

可发现质数p与比它小的质数相乘得到的乘积,一定在之前被那么更小的质数筛过。那么筛选的时候直接从p2p^2开始筛选,避免重复。

const int N=1e6+5;
bool vis[N];
void esieve(int n){//标记0~n的数字的质数状态,并统计质数个数
    vis[0]=vis[1]=1;
	for(int i=2;i*i<=n;i++){//标记剩下的2~n的数字的状态 优化:到根号n即可停止
		if(vis[i]==0){//判断i是不是质数 
			for(int j=i*i;j<=n;j+=i){//遍历范围内的i的倍数 从i*i开始,减少重复筛选
				vis[j]=1;//将倍数标记为1(非质数)
			}
		}
	}
}

时间复杂度O(nloglogn)O(nloglogn)

复杂度分析链接:https://www.cnblogs.com/dc93/p/3930362.html

习题巩固

题目描述

今天是贝茜的生日,为了庆祝自己的生日,贝茜邀你来玩一个游戏。

贝茜让 N (1N1051\leq N\leq 10^5 ) 头奶牛坐成一个圈。除了11号与NN号奶牛外,ii 号奶牛与i1i−1号和 i+1i+1 号奶牛相邻。NN号奶牛与 11 号奶牛相邻。农夫约翰有一个桶,里面装满了很多纸条,每一张纸条上写了一个不一定是独一无二的 1110610^6 的数字。

接着每一头奶牛 ii 从桶中取出一张纸条AiA_i 。每头奶牛轮流走上一圈,同时拍打所有手上数字能整除在自己纸条上的数字的牛的头,然后做回到原来的位置。牛们希望你帮助他们确定,每一头奶牛走上一圈时能够拍打的牛的数量。

输入格式

第一行包含一个整数n

第二行到n+1行每行包含一个整数AiA_i

输出格式

共n行,每行包含一个整数,代表被拍打的牛的数量

样例输入

5
2
1
2
3
4

样例输出

2
0
2
1
3

分析

根据题意概括一下,就是给出数列a,对于第i项的aia_i求出数列中有多少个是他的约数。

暴力

遍历其它元素,统计他的约数的个数即可。复杂度O(n2)O(n^2)

for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
        if(i!=j&&a[i]%a[j]==0){
            cnt++;
        }
    }
}

优化

利用埃氏筛的思想,统计数组中的内容,对它的倍数做的贡献即可。

#include <iostream>
#include <cstdio>
using namespace std;
const int N=1e6+5;
int a[N],cnt[N],M=0;//cnt[x]=k x在数列中的约数个数为k
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		cnt[a[i]]++;//记录次数
		M=max(M,a[i]);//求值得最大范围
	}
	for(int i=M;i>=1;i--){//从到大小进行遍历
		if(!cnt[i]) continue;//没出现过的直接跳过
		for(int j=2;j*i<=M;j++){//找范围内的i的倍数
			if(cnt[j*i])//如果倍数也是在数列中的值
				cnt[j*i]+=cnt[i];//倍数对应的在数列中的因数个数增加
		}
	}
	for(int i=1;i<=n;i++){
		cout<<cnt[a[i]]-1<<endl;//注意要去掉自己
	}
	return 0;
}

第二课时

欧拉筛

模拟出埃氏筛的筛选过程。

即便进行了一定的优化,但是依旧存在数字被重复筛选的问题。它的复杂度依旧不变O(nloglogn)O(nloglogn)

此时,若能让每个数字只被筛选一次,必然能大大地降低时间复杂度,减少运行时间,理论上的时间复杂度为O(n)O(n)

这种每个数字只被筛一遍的筛法叫做欧拉筛,也被称作线性筛。

那么,关键是,如何实现这一算法?

我们依旧利用唯一分解定理来实现。之前的埃氏筛,利用到了唯一分解定理的前半段,这次我们利用好它的后半截。

每个大于1的自然数,要么本身就是质数,要么可以写为2个或以上的质数的积,而且这些质因子按大小排列之后,写法仅有一种方式

合数对应的分解因式,只要我们将这小质因子按大小排列好,那么分解式子就是唯一的。

我们要利用他的唯一性来做文章。我们只要能不重复的构造出这样的“唯一的质数序列”,那么必然不会重复筛选了。

此时我们将任意的一个数字都可看做为一个唯一的质数序列,如1212可看作是序列2×2×32\times 2\times 3 。此时我们只要再找个质数,与这样的质数序列组合即可构成新的质数序列。

需要注意的是,如何防止重复?也就是怎么保证构造出来的序列的唯一性?我们新的质数组合进去之后,只要不破坏序列整体的有序性,即可实现不重复。假设,我们每次将质数是加在序列的前头,那么只需要P新质数序列的最小质因子P_{新质数}\leq 序列的最小质因子 即可保证整体有序。

例如 通过 2×2×32\times 2\times 3 进行新序列的组合的话,只能加质数2,形成新序列2×2×2×3=242\times 2\times 2\times 3=24。如果是序列15=3×515=3\times 5的话只能和2,3组合,形成新序列2×3×5=302\times 3\times5=303×3×5=453\times 3\times5=45

这样,我们在实现的时候就要在之前的基础上多一个质数表存放质数,好利用这些质数构成质数序列。

模板

时间复杂度O(n)O(n)

const int N=1e8+5;
bool vis[N];//标记数组
int prime[N/10];//质数表,存放质数
int erla(int n){
	vis[0]=vis[1]=1;//0.1不是质数
	int cnt=0;//统计质数的个数
	for(int i=2;i<=n;i++){
		if(!vis[i]){//判断i是不是质数
			prime[cnt++]=i;//将质数存到质数表中
		}
		//遍历质数表 新序列 prime[j]*i
		for(int j=0;prime[j]*i<=n&&j<cnt;j++){
			vis[prime[j]*i]=1;//标记组成的序列为非质数
			if(i%prime[j]==0) break;//prime[j]是i的最小质因子 ,不能继续组合,避免重复
		}
	}
	return cnt;//返回质数个数
}

思考:14行操作的意义,思考为什么这么做就能不重复地筛选?

回答:质数表中的质数是从小到大的,在遍历质数表时,可看做满足pji的最小值因子p_j\le i的最小值因子 ,遍历到的质数与i构成的序列就不重复。当满足整除条件时,prime[j]就是等于i的最小质因子,再遍历下去,就不满足质数从小到大的关系。

习题巩固

哥德巴赫猜想(升级版)

问题描述

求1~N中素数的个数。

输入格式

一行一个整数N。

输出格式

一行一个数,表示素数的个数。

输入样例

10

输出样例

4

数据范围

对于40%的数据,1N1061\leq N\leq 10^6

对于80%的数据,1N1071\leq N\leq 10^7

对于100%的数据,1N1081\leq N\leq 10^8

分析

注意数据范围,套欧拉筛模板即可。

第三课时

欧拉函数

​ 在数论中,对正整数n欧拉函数是小于或等于n的正整数中与n互质的数的数目。

​ 例如ϕ(1)=1,(1)\phi(1)=1,(1),ϕ(8)=4,(1,3,5,7)\phi(8)=4,(1,3,5,7)。如果i是素数,则ϕ(i)=i1\phi(i)=i-1

设p为质数

三个性质:

  1. ϕ(p)=p1\phi(p)=p-1
  2. i mod p=0,ϕ(i×p)=p×ϕ(i)i\ mod\ p = 0,\phi(i\times p)=p\times \phi(i)
  3. i mod p0,ϕ(i×p)=(p1)×ϕ(i)i\ mod\ p \ne 0,\phi(i\times p)=(p-1)\times \phi(i)

实现代码

时间复杂度O(n)O(n)

bool vis[N];//标记数组
int prime[N];//质数表,存放质数
int phi[N];
int erla(int n){
	vis[0]=vis[1]=1;//0.1不是质数
	int cnt=0;//统计质数的个数
	phi[1]=1;//1的欧拉函数值是1
	for(int i=2;i<=n;i++){
		if(!vis[i]){//判断i是不是质数
			prime[cnt++]=i;//将质数存到质数表中
			phi[i]=i-1;//性质1
		}
		//遍历质数表 新序列 prime[j]*i
		for(int j=0;prime[j]*i<=n&&j<cnt;j++){
			vis[prime[j]*i]=1;//标记组成的序列为非质数
			if(i%prime[j]==0){
				phi[i*prime[j]]=prime[j]*phi[i];//性质2
				break;//prime[j]是i的最小质因子 ,不能继续组合,避免重复
			}else{
				phi[i*prime[j]]=(prime[j]-1)*phi[i];//性质3
			}
		}
	}
	return cnt;//返回质数个数
}

Q.E.D.


( ノ^ω^)ノ゚ 稻 花 香 里 说 丰 年 , 听 取 WA 声 一 片 。(╥╯^╰╥)