素数与素数筛法
课上练习
知识总结
素数与素数筛法-知识总结
素数与素数筛法-知识总结 素数 对于大于1的自然数： 除了1和它本身，不能被其它自然数整除的数是素数； 除了1和它本身，能被其它自然数整除的数是合数。
大于1的自然数，如果不是质数就是合数，2是最小的素数，也是唯一的偶数素数。
素数判定 如果要检查自然数n是不是素数，只需要检查n是否能整除根号n以内的数即可，如果不能整除除1外的任何整数，则n是质数。
🖥️代码模版
1#include<iostream>
2#include<cmath> // 包含cmath库，用于调用sqrt函数
3using namespace std;
4
5// 函数isPrime用于判断一个整数n是否为素数
6bool isPrime(int n) {
7 // 对n小于2的情况直接返回false，因为素数定义为大于1的自然数
8 if (n < 2) {
9 return false;
10 }
11
12 // 试除法的核心思想是试着将n除以2到sqrt(n)之间的所有整数
13 // sqrt函数用于计算n的平方根，因为如果n为合数，它必有一个因子不大于其平方根
14 int rootN = sqrt(n);
15 for (int i = 2; i <= rootN; i++) {
16 // 如果n能被i整除，则n不是素数，返回false
17 if (n % i == 0) {
18 return false;
19 }
20 }
21 // 如果上面的循环完成后没有找到能整除n的数，则n是素数，返回true
22 return true;
23}
24
25int main() {
26 int number;
27 cout << "Enter a number: "; // 提示用户输入一个数
28 cin >> number; // 从标准输入读取一个整数
29
30 // 调用isPrime函数判断用户输入的数是否为素数
31 if (isPrime(number)) {
32 cout << number << " is a prime number." << endl; // 如果是素数，输出提示信息
33 } else {
34 cout << number << " is not a prime number." << endl; // 如果不是素数，输出提示信息
35 }
36 return 0; // 程序正常结束
37}素数筛法 素数筛法是用来找出一定范围内的所有的素数的算法，常用的素数筛法有埃式筛法（Eratosthenes' Sieve）和欧式筛法（Euler's Sieve）。
埃式筛法 埃式筛法是一种简单直观的筛选素数方法，它的基本步骤如下： 初始化：创建一个布尔数组，长度为n+1（假设我们要筛选的范围是从2到n），并将所有元素初始化为true。数组的索引代表数字本身，true代表该索引数字是素数。 筛选：从第一个素数2开始，依次将每个素数的倍数标记为非素数（设为false）。这个过程从2开始，一直进行到n\sqrt{n}n，因为超过n\sqrt{n}n的倍数在之前已经被标记过了。 收集结果：最后，数组中仍然标记为true的索引位置对应的数字就是素数。 埃式筛法的时间复杂度是O(nloglogn)，空间复杂度是O(n)，适用于解决较小范围的素数筛选问题。
🖥️代码模版
1#include<iostream>
2#include<cmath>
3using namespace std;
4
5// 定义一个布尔数组，用来标记每个数字是否是素数
6bool isPrime[105] = {0};
7
8// 埃拉托斯特尼筛法的实现
9void eratosthenes(int n) {
10 // 使用memset将isPrime数组的所有值初始化为true
11 memset(isPrime, 1, sizeof(isPrime));
12 int rootN = sqrt(n); // 计算n的平方根，减少不必要的遍历
13 // 从2开始遍历到n的平方根
14 for (int i = 2; i <= rootN; i++) {
15 if (isPrime[i]) { // 如果i是素数
16 // 将i的所有倍数标记为非素数
17 for (int j = i * i; j <= n; j += i) {
18 isPrime[j] = false;
19 }
20 }
21 }
22}
23
24int main() {
25 int n = 0; // 用户输入的数
26 cin >> n; // 读取用户输入
27 eratosthenes(n); // 调用埃拉托斯特尼筛法
28 // 遍历数组，打印所有标记为素数的数
29 for (int i = 2; i <= n; i++) {
30 if (isPrime[i]) {
31 cout << i << " ";
32 }
33 }
34 cout << endl;
35 return 0;
36}欧式筛法 相对于埃式筛法，欧式筛法在执行效率上更有优势，特别是在处理大范围的数据时。它的基本思想是尽可能减少重复的非素数标记操作。其步骤包括： 初始化：同样创建一个布尔数组和一个空的素数列表。 筛选：遍历每个数字，如果这个数字是素数，则将其添加到素数列表中。接着，遍历素数列表，用每个素数去乘以当前数字，标记得到的乘积为非素数。关键点是，对于每个数字，只用它之前的素数进行标记，并且在遇到第一个能整除它的素数时停止标记。 优化：欧式筛法确保每个合数只被它的最小质因数筛掉，从而减少了重复操作。 欧式筛法的时间复杂度接近于O(n)，空间复杂度也是O(n)，适用于大范围的素数筛选问题。
🖥️代码模板
1#include <vector>
2#include <iostream>
3using namespace std;
4
5vector<int> primes; // 存放素数的列表
6bool isPrime[105] = {0}; // 标记数组，记录是否是素数
7
8// 线性筛法的实现
9void linearSieve(int n) {
10 // 使用memset将isPrime数组的所有值初始化为true
11 memset(isPrime, 1, sizeof(isPrime));
12 for (int i = 2; i <= n; i++) {
13 if (isPrime[i]) { // i 为素数
14 // 将 i 添加到素数列表
15 primes.push_back(i);
16 }
17 // 用已有的素数去筛 i 的倍数
18 for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) {
19 isPrime[i * primes[j]] = false; // 标记为非素数
20 if (i % primes[j] == 0) break; // 关键：保证最小素因子原则
21 }
22 }
23}
24
25int main() {
26 int n = 0; // 用户输入的数
27 cin >> n; // 读取用户输入
28 linearSieve(n); // 调用线性筛法
29 // 遍历数组，打印所有标记为素数的数
30 for (int i = 0; i < primes.size(); i++) {
31 cout << primes[i] << " ";
32 }
33 cout << endl;
34 return 0;
35}️课后作业
☝️总结作业
总结作业非常重要，请务必认真完成✔️
- 请写出欧式筛法的主要过程。
- 请写出线性筛法的主要过程。
✌️编程作业
考试只有一次提交机会，请务必本地检查正确后再提交❇️
- 含k个2的质数：L3054