《 CSP - J 初级组 算法 中 数学 》
Day03 - 初等数论 (下 )
课程大纲
同余
定义 1: ： 如果 a 和 b 都是整数而 m 是一个固定的正整数，则当 m|(a - b)( 即 m 能够整除
a - b) 时，我们就说 a,b 对模 m 同余，记作：
当 m不能整数 a-b时，则我们就说 a,b 对模 m不同余，记作：
同余
判断以下式子是否正确（即是否同余）
( √ )
( √ )
9能整除 27
8不能整除 161
同余
判断以下式子是否正确（即是否同余）
( × )
50 能整除 100
如果有两个整数 a,b ，其中 b>0 ，如果 a= bq+r ， q,r 都是整数，且 0≤r<b
-7=50* (?) +r
a=bq+ r
同余
例 1 今天是星期一，再过 100 天是星期几？ 答案： 星期三
例 2 如果 98 和 66 除以同一个数都余 2，求这个数是多少？
x能整除 32
32 的约数有 ： 1、 2、 4、 8、 16 、 32 除数要大于余数 4、 8、 16 、 32
答案： 4、 8、 16 、 32
同余
例 3 如果 82,98 和 66 除以同一个数都余 2 ，求这个数是多少？
16 的约数有 ： 1、 2、 4、 8、 16 除数要大于余数 4、 8、 16
答案： 4、 8、 16
同余
例 4 如果 101 和 80 除以同一个大于 1 的数，余数相同，求这个数是多少？ 答案： 3、 7、 21
x能 整除 21
21 的约数有 ： 1、 3、 7、 21 除数要大于余数 3、 7、 21
同余
例 5 如果 87,52 和 31 除以 A （ A>1 ）的余数相同，求 A 是多少？ 答案： 7
同余
例 6 如果 141 和 239 除以同一个大于 1 的数，余数分别为 a 和 a+18 , 求这个数是多少 ?
答案： 20 、 40 、 80
80 的约数有 ： 1、 2、 4、 5、 8、 10 、 16 、 20 、 40 、 80 20 、 40 、 80
20 、 40 、 80
验证，因为有可能 a+18 大于除数（比如 151 和 249 就无解）
20 、 40 、 80
同余
和的余数 = 余数的和
积的余数 = 余数的积
else 处理条件不满足 质数筛
质数判定、埃氏筛法、线性筛法
质数与合数
定义 2: ： 一个大于 1 的正整数，只能被 1 和它本身整除，不能被其它正整除整除，这
样的正整数叫做素数（也叫做质数）。
eg. 都是 质数
定义 3: ： 一个正整数除了能被 1 和它本身整除以外，还能被另外的正整数整除，这
样的正整数叫做复合数（也叫做合数）。
eg. 都是 合数
Q3 : 如何判定一个数是质数？
Q4 : 如何判定一个数是合数？
开根号法判定质数
引理 2: ： 如果 a 是一个大于 1 的整数，而所有 ≤ a的 素数都除不尽 a, 则 a 是素数。
Step 1: 证明（ 1） ：如果 a被 > 1 而 ≤ a的整数都除不尽，则 a是素数
bool isPrime (int n){
if (n == 0 || n == 1) return false ;
for (int i = 2; i <= sqrt(n); i++){
if ( n%i == 0){
return false ;
}
}
return true ;
}
假设 a是合数，则 a= bc , 而 a被 > 1 而
≤ a的整数都除不尽，则 b> a, c>
a,则 bc >a, 这与 bc =a 是矛盾的。
开根号法判定质数
质数筛
质数筛（素数筛）： 给定一个整数，求出之间的所有质数 (素数 )，这样的问题为质数筛 (素
数的筛选问题 )。
1 2 3 4 5 6 7 8 9 10 11
12 13 14 15 16 17 18 19 20 21 22
23 24 25 26 27 28 29 30 31 32 33
34 35 36 37 38 39 40 41 42 43 ···
埃氏筛法
埃氏筛法
埃拉托斯特尼 Eratosthenes
（前 276 年－前 194 年）
古希腊数学家、诗人、天文学家
埃拉托斯特尼筛法
测量地球周长
基本思想：任意 整数 x的倍数 2x,3 x,…… 都不是质数
任意 质数 x的倍数 2x,3 x,…… 都不是质数
算术基本定理
埃氏筛法
Step 1 ：首先将 0、 1排除：
Step 2 ：创建从 2到 n的连续整数列表， [2,3,4,…,n] ；
Step 3 ：初始化 p = 2 ，因为 2是最小的质数；
Step 4: ：枚举所有 p的倍数 (2p,3p,4p,…) ，标记为非质数
（合数）；
Step 5 ：找到下一个没有标记且大于 p的数。如果没有，结
束运算；如果有，将该值赋予 p，重复步骤 4;
Step 6 ：运算结束后，剩下所有未标记的数都是找到的质
数。
埃氏筛法
int Eratosthenes( int n){
for (int i = 1;i <= n; i++) is_p [i]= 1;
memset (prime, 0,sizeof (prime));
is_p [1] = is_p [0] = 0;
for (int i = 1;i <= n;i ++){
if (! is_p [i]) continue ;
prime[++tot]= i;//prime[] 存储了 [1,n] 的所有质数
for (int j = i*2; j <= n; j+= i) is_p [j]= 0;//j
为合数
}
return tot;
}
Step 1 ：首先将 0、 1排除：
Step 2 ：创建从 2到 n的连续整数列表，
[2,3,4,…,n] ； Step 3 ：初始化 p = 2 ，因为 2
是最小的质数；
Step 4: ：枚举所有 p的倍数 (2p,3p,4p,…) ，标记
为非质数（合数）；
Step 5 ：找到下一个没有标记且大于 p的数。如果
没有，结束运算；如果有，将该值赋予 p，重复步
骤 4;
Step 6 ：运算结束后，剩下所有未标记的数都是
找到的质数。
埃氏筛法
1 2 3 4 5 6 7 8 9 10 11
12 13 14 15 16 17 18 19 20 21 22
23 24 25 26 27 28 29 30 31 32 33
34 35 36 37 38 39 40 41 42 43 ···
03初等数论（下）信息学奥赛CSP-J数学课件-初等数论（下）