埃氏算法C++实现: 快速输出质数( 素数 )

目次
1.简介
算法原理
算法特点
应用场景
2.一般求素数方法
3.埃氏算法求素数
3.1.无动态分配
3.2.有动态分配

---

1.简介

‌埃氏算法（Eratosthenes Sieve）‌，全称为埃拉托斯特尼筛法，是一种由古希腊数学家埃拉托斯特尼在公元前3世纪提出的古老而经典的算法，用于计算一定范围内的素数。其根本头脑是通过从小到大遍历每个数字，并将其所有倍数标记为非质数，从而逐步排除所有非质数，最终得到所有的素数。‌
算法原理

埃氏筛法的根本原理是：要得到自然数n以内的全部素数，必须把不大于√n的所有素数的倍数剔除，剩下的就是素数。具体步调如下：

• 初始化：创建一个布尔范例的数组（或列表），用于表示范围内的所有数字，初始时将所有元素标记为“true”，表示都是素数（或待检定的数）。
  
• 遍历与筛选：从2开始遍历数组中的每个数。如果当前数字被标记为素数（即为“true”），则进行下一步筛选操纵；否则，跳过该数字。对于当前素数p，从p的平方开始，将p的倍数（如2p、3p、4p等）标记为非质数（即为“false”），由于p的所有小于p平方的倍数在之前的步调中已经被更小的素数筛选过了。
  
• 重复操纵：继承向后遍历，重复步调2的筛选过程，直到遍历完整个范围。
  
• 输出效果：遍历结束后，所有未被标记为非质数（仍为“true”）的数字都是素数，将其输出即可。
  

算法特点

• ‌简单直观‌：埃氏筛法的原理简单易懂，实现起来也较为直接。
  
• ‌高效性‌：虽然算法的时间复杂度为O(nloglogn)，但在实际应用中，它仍然是探求一定范围内素数的高效方法之一。
  
• ‌汗青悠久‌：作为一种古老的算法，埃氏筛法在数学史上占有告急地位，是素数研究的基础工具之一。
  

应用场景

埃氏筛法广泛应用于数论、暗码学、计算机科学等领域，特别是在必要快速生成大量素数时，其高效性得到了充分体现。例如，在暗码学中的RSA算法中，就必要生成大量的素数作为密钥的基础。
2.一般求素数方法

1. #include <iostream>
2. #include <cmath>
4. using namespace std;
6. bool is_prime(int num) {
7.     if (num <= 1) return false;
8.     if (num == 2) return true; // 2 is the only even prime number
9.     if (num % 2 == 0) return false; // other even numbers are not primes
10.    
11.     int sqrt_num = static_cast<int>(sqrt(num));
12.     for (int i = 3; i <= sqrt_num; i += 2) {
13.         if (num % i == 0) return false;
14.     }
15.     return true;
16. }
18. void find_primes_up_to(int n, int* primes, int& prime_count) {
19.     prime_count = 0;
20.     for (int i = 2; i <= n; ++i) {
21.         if (is_prime(i)) {
22.             primes[prime_count++] = i;
23.         }
24.     }
25. }
27. int main() {
28.     int n;
29.     cout << "Enter a number: ";
30.     cin >> n;
31.    
32.     // Assuming the maximum number of primes is n/2 (an overestimate)
33.     int* primes = new int[n / 2];
34.     int prime_count;
35.    
36.     find_primes_up_to(n, primes, prime_count);
37.    
38.     cout << "Prime numbers up to " << n << " are: ";
39.     for (int i = 0; i < prime_count; ++i) {
40.         cout << primes[i] << " ";
41.     }
42.     cout << endl;
43.    
44.     delete[] primes; // Free the allocated memory
45.     return 0;
46. }

复制代码

3.埃氏算法求素数

3.1.无动态分配

1. #include <iostream>
2. #include <cmath>
4. using namespace std;
6. bool is_prime(int num) {
7.     if (num <= 1) return false;
8.     if (num == 2) return true; // 2 is the only even prime number
9.     if (num % 2 == 0) return false; // other even numbers are not primes
10.    
11.     int sqrt_num = static_cast<int>(sqrt(num));
12.     for (int i = 3; i <= sqrt_num; i += 2) {
13.         if (num % i == 0) return false;
14.     }
15.     return true;
16. }
18. void find_primes_up_to(int n, int primes[], int& prime_count) {
19.     prime_count = 0;
20.     for (int i = 2; i <= n; ++i) {
21.         if (is_prime(i)) {
22.             primes[prime_count++] = i;
23.         }
24.     }
25. }
27. int main() {
28.     int n;
29.     cout << "Enter a number: ";
30.     cin >> n;
31.    
32.     // Assuming the maximum number of primes is n/2 (an overestimate)
33.     int primes[n / 2];
34.     int prime_count;
35.    
36.     find_primes_up_to(n, primes, prime_count);
37.    
38.     cout << "Prime numbers up to " << n << " are: ";
39.     for (int i = 0; i < prime_count; ++i) {
40.         cout << primes[i] << " ";
41.     }
42.     cout << endl;
43.    
44.     return 0;
45. }

复制代码

3.2.有动态分配

1. #include <iostream>
2. #include <cmath>
4. using namespace std;
6. bool is_prime(int num) {
7.     if (num <= 1) return false;
8.     if (num == 2) return true; // 2 is the only even prime number
9.     if (num % 2 == 0) return false; // other even numbers are not primes
10.    
11.     int sqrt_num = static_cast<int>(sqrt(num));
12.     for (int i = 3; i <= sqrt_num; i += 2) {
13.         if (num % i == 0) return false;
14.     }
15.     return true;
16. }
18. void find_primes_up_to(int n, int* primes, int& prime_count) {
19.     prime_count = 0;
20.     for (int i = 2; i <= n; ++i) {
21.         if (is_prime(i)) {
22.             primes[prime_count++] = i;
23.         }
24.     }
25. }
27. int main() {
28.     int n;
29.     cout << "Enter a number: ";
30.     cin >> n;
31.    
32.     // Assuming the maximum number of primes is n/2 (an overestimate)
33.     int* primes = new int[n / 2];
34.     int prime_count;
35.    
36.     find_primes_up_to(n, primes, prime_count);
37.    
38.     cout << "Prime numbers up to " << n << " are: ";
39.     for (int i = 0; i < prime_count; ++i) {
40.         cout << primes[i] << " ";
41.     }
42.     cout << endl;
43.    
44.     delete[] primes; // Free the allocated memory
45.     return 0;
46. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。