埃氏算法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.一般求素数方法
#include <iostream>
#include <cmath>using namespace std;bool is_prime(int num) {if (num <= 1) return false;if (num == 2) return true; // 2 is the only even prime numberif (num % 2 == 0) return false; // other even numbers are not primesint sqrt_num = static_cast<int>(sqrt(num));for (int i = 3; i <= sqrt_num; i += 2) {if (num % i == 0) return false;}return true;
}void find_primes_up_to(int n, int* primes, int& prime_count) {prime_count = 0;for (int i = 2; i <= n; ++i) {if (is_prime(i)) {primes[prime_count++] = i;}}
}int main() {int n;cout << "Enter a number: ";cin >> n;// Assuming the maximum number of primes is n/2 (an overestimate)int* primes = new int[n / 2];int prime_count;find_primes_up_to(n, primes, prime_count);cout << "Prime numbers up to " << n << " are: ";for (int i = 0; i < prime_count; ++i) {cout << primes[i] << " ";}cout << endl;delete[] primes; // Free the allocated memoryreturn 0;
}
3.埃氏算法求素数
3.1.无动态分配
#include <iostream>
#include <cmath>using namespace std;bool is_prime(int num) {if (num <= 1) return false;if (num == 2) return true; // 2 is the only even prime numberif (num % 2 == 0) return false; // other even numbers are not primesint sqrt_num = static_cast<int>(sqrt(num));for (int i = 3; i <= sqrt_num; i += 2) {if (num % i == 0) return false;}return true;
}void find_primes_up_to(int n, int primes[], int& prime_count) {prime_count = 0;for (int i = 2; i <= n; ++i) {if (is_prime(i)) {primes[prime_count++] = i;}}
}int main() {int n;cout << "Enter a number: ";cin >> n;// Assuming the maximum number of primes is n/2 (an overestimate)int primes[n / 2];int prime_count;find_primes_up_to(n, primes, prime_count);cout << "Prime numbers up to " << n << " are: ";for (int i = 0; i < prime_count; ++i) {cout << primes[i] << " ";}cout << endl;return 0;
}
3.2.有动态分配
#include <iostream>
#include <cmath>using namespace std;bool is_prime(int num) {if (num <= 1) return false;if (num == 2) return true; // 2 is the only even prime numberif (num % 2 == 0) return false; // other even numbers are not primesint sqrt_num = static_cast<int>(sqrt(num));for (int i = 3; i <= sqrt_num; i += 2) {if (num % i == 0) return false;}return true;
}void find_primes_up_to(int n, int* primes, int& prime_count) {prime_count = 0;for (int i = 2; i <= n; ++i) {if (is_prime(i)) {primes[prime_count++] = i;}}
}int main() {int n;cout << "Enter a number: ";cin >> n;// Assuming the maximum number of primes is n/2 (an overestimate)int* primes = new int[n / 2];int prime_count;find_primes_up_to(n, primes, prime_count);cout << "Prime numbers up to " << n << " are: ";for (int i = 0; i < prime_count; ++i) {cout << primes[i] << " ";}cout << endl;delete[] primes; // Free the allocated memoryreturn 0;
}