一、观看PPT教程
【01】初等数论（一）
二、练习题（不清楚回头查看有关PPT）
【01】有关整除的描述，错误的是：①设a, b是任意两个整数，其中b≠0，如果a除以b的商为整数且余数为0，我们就是说a整除b，或者a能被b整除，记作b|a。
②被除数a ÷ 除数b = 商 ... 余数。如果商为整数并且余数为0，说明a能被b整除。③如果b|a，那么我们把b叫做a的因数(约数)，把a叫做b的倍数。
【02】说一说下面数对中，第一个数能被第二个数整除的：
① 10，3 ② 20，5 ③ 13，5【03】有关求余运算符的描述，错误的是：
①C++提供了一个用于计算余数的运算符：%
②10 % 3 = 1，即10除以3的余数是1，说明10不能被3整除。
③30 % 5 = 0，即30除以5的余数是0，说明30能被5整除。④如果整数a不能被整数b整除，那么a一定大于b。
【04】下面是整除的性质，错误的是：
①整除的传递性：如果b|a，c|b，则c|a。
②同倍整除性：如果b|a，c是一个非0整数，那么cb|ca。
③除数和整除性：如果b|a，c|a，那么(b+c)|a。
④倍数整除性：如果c|a，那么对于任何整数d，c|da。
⑤被除数和整除性：如果c|a，c|b，则对于任何整数m,n，有c|(ma+nb)。
⑥相等判定：如果a|b，b|a，则a=b。
【05】编程题：能同时被3、5整除的数。
【06】有关最大公因数的定义的描述，错误的是：
①设a, b是任意两个整数（是指正整数，下同），若整数d既是a的因数，也是b的因数，那么d就叫做a和b的公因数。
②所有公因数中最大的一个就是最大公因数（最大公约数），记作gcd(a, b)。
③如果gcd(a, b) = 1, 那么a和b都是质数。
【07】下面有六个是最大公因数的性质，请选出语言描述错误的项目：
①当b|a时，gcd(a, b) = b。语言描述：一个正整数能被另一个正整数乘除，那么它们的最大公约数是另一个正整数。
②a, b的所有公因数都是gcd(a, b)的因数。语言描述：两个正整数的所有公因数都是最大公因数的因数。
③若a, b是正整数，m为任一正整数，则有gcd(am, bm) = gcd(a, b) × m。语言描述：两个正整数与第三个正整数分别相乘的积的最大公因数是原来这两个正整数的最大公因数与第三个正整数的积。
④若gcd(a, b)=1，c为任一正整数，则有gcd(ac, b)=gcd(c, b)。语言描述：任一正整数，与两个互质数之中的一个的积，这个积与两个互质数之中的另一个正整数的最大公因数，等于这个数与其的最大公因数。
⑤若gcd(a, b)=1，b|ac，则有b|c。语言描述：任一正整数与两个互质数中的一个的乘积能被另一个正整数整除，那么这个数也能整除另一个正整数。
⑥若a,b,d是三个任意正整数，则gcd(a, b) = d的充分必要条件是gcd(a/d, b/d)=1。语言描述：如果一个正整数是另外两个正整数的最大公因数，那么另外两个正整数分别与这个正整数的商是互质数；如果两个正整数分别与另一个正整数的商是互质数，那么另一个正整数是这两个正整数的最大公因数。
【08】辗转相除法也叫欧几里得算法，是用来求解最大公因数的常用方法，最早出现在古希腊数学家“几何之父”欧几里得的《几何原本》中。原理的代数描述是：如果两个整数a和b，另有整数c=a%b；那么a和b的最大公约数就是b和c的最大公约数，即gcd(a, b)=gcd(b, c)。请用整除和最大公约数的有关性质对它进行简单证明。
【09】请完善辗转相除法的第③步骤：
①用a除以b，得到余数r;
②如果余数为0，则此时的b即为最大公因数；
③④不断重复第①步和第③步，直到余数为0。【10】a = 46，b=32，利用辗转相除法求gcd(a, b)。（非编程，写出运算步骤）。
【11】编程题：最大公约数
【12】有关最小公倍数的定义的描述，错误的是：
①设a, b是两个整数，若整数d既是a的倍数，也是b倍数，那么d就叫做a和b的公倍数，所有公倍数中最小的一个就是最小公倍数，记作lcm(a, b)。
②如果a, b都是质数，则lcm(a, b) = a × b；反之，如果lcm(a, b) = a × b，则a, b都是质数。
③如果a, b互质，则lcm(a, b) = a × b。【13】最小公倍数的性质，描述错误的是：
①若a、b是任意两个正整数，则a、b的所有公倍数都是lcm(a, b)的倍数。②如果a、b是任意两个正整数，那么lcm(a, b)的所有倍数（n×lcm(a, b)，n=1，2，……）都是a、b的公倍数。③若a、b是任意两个正整数，则它们的最小公倍数等于它们的乘积与它们的最大公约数的商。④若a、b是任意两个正整数，则它们的最小公倍数等于它们分别与它们的最大公约数的商的乘积。
⑤两个互质的正整数a、b的最小公倍数是它们的乘积。
⑥如果a、b是任意两个正整数，那么它们的乘积一定是它们最小公倍数的倍数。
【14】有关质数和合数的定义的描述，错误的是：
①质数又称素数。
②一个大于1的正整数，除了1和它本身外，不能被其他正整数整除的数叫做质数，否则称为合数。
③1既是质数也是合数。
【15】质数的判断方法之一——朴素算法（根据定义的模拟算法）：判断一个整数n是否是质数，一般情况下，只需要将2到n-1逐一进行试除，如果都不能整除，那么n就是一个质数。请补全下面的朴素算法代码：
·
·
·
·
·
·
·
·
·
·
·
bool isPrime(int n){
}
【16】编程题：找素数
【17】质数筛（Prime Sieve）的有关描述，错误的是：
①质数筛是一种用于找出一定范围内所有质数的算法。②它通过逐步排除合数的方法，最终得到质数的列表。③质数筛可以高效地找出较小范围内的质数，并被广泛应用于数论、密码学等领域。
④质数筛相对传统质数判断方法（朴素算法，2到n乘除2的试除）具有更高的效率。⑤常用的质数筛包括埃氏筛和线性筛（又称欧拉筛）。
【18】有关埃氏筛的描述，错误的是：
①要得到正整数n以内（包括）的全部质数，只需将不大于根号n的所有质数倍数（1倍除外）都删除，剩下的就是质数。
②埃氏筛基于一个数学原理——任何合数都可以表示为质数的乘积。
③埃氏筛的时间复杂度 T = O(n)。
【19】在电子表格里，使用埃氏筛找出2到100（包括2和100）以内的所有质数。
【20】下面是埃氏筛的步骤，把描述错误的选出来：
①设置一个bool类型的数组，用于标记数字是否被删除（PPT教程有误，这里更正），将数组初始化为false；②从下标2开始，2是质数，接下来将2的倍数（自身除外）下标的位置都设为true，表示减这些数删除；③继续向后找数值为false（还没删除），3是质数，接下来将3的倍数（自身除外）下标的位置都设为true，表示将这些数删除；
④如此类推，将n的平方根的地板值（包括）以内所有质数的倍数位置（除了它自身以外）都设置为true;
⑤最后遍历数组，如果Prime[i]为false，则i是质数，输出i。
【21】编程题：用埃氏筛输出100（包括）以内正整数中的所有质数。
【22】埃氏筛在筛选的过程中，某些数字会被重复筛选，降低算法的效率，举例说明。
【23】有关线性筛的描述，错误的是：
①线性筛（又称欧拉筛）算法，用于找到给定范围内的所有质数。
②线性筛算法中，每个合数只会被它的最小质因数筛去。
③线性筛算法中，每个数最多只会被处理一次。
④线性筛基于一个数学原理——任何合数都可以表示为质数的乘积。⑤线性筛的时间复杂度 T = O(n²)。
【24】线性筛步骤，错误的是：
①创建一个布尔数组Prime，将所有元素初始化为true；
②创建一个数组a，用于储存筛选出来的质数；
③从2开始遍历岛指定的上限数n：如果Prime[i]为true，表示i是质数，将其加入质数数组a；对于素数数组中的每个素数p，将i*p标记为非素数，即将Prime[i*p]设为false。④完成遍历后，素数数组a中储存的非0数即为从2到n之间的所有素数。
【25】编程题：请用线性筛查找2到100（包括2和100）之间的所有质数并输出。【26】用整数数组记录删除次数并输出，对比两种质数筛的删除次数，然后举例说明为什么线性筛能保证每个合数只标记一次。