使用埃拉托色尼筛查找2至N内的质数

拼搏现实的明天。 2022-12-14 09:05 86阅读 0赞

筛选步骤：

（1）先把1删除（现今数学界1既不是[质数][Link 1]也不是合数）

（2）读取队列中当前最小的数2，然后把2的倍数删去

（3）读取队列中当前最小的数3，然后把3的倍数删去

（4）读取队列中当前最小的数5，然后把5的倍数删去

（5）读取队列中当前最小的数7，然后把7的倍数删去

（6）如上所述直到需求的范围内所有的数均删除或读取

![20160703235154990][]

输入上限N，查找2-N内的所有质数，代码如下：

#include <iostream>
    using std::cout;
    using std::cin;
    using std::endl;
    
    void process_prime(bool *p, int max_n, int n);
    int main(void) {
    	int max_n = 0;
    	int count = 0;//质数的个数
    	cout << "Cauculator primes up to what number? ";
    	cin >> max_n;
    	//分配内存
    	bool *p = new bool[max_n + 1];
    	//初始化
    	for (int i = 2; i <= max_n; i++) {
    		p[i] = true;
    	}
    	//查找质数
    	for (int i = 2; i <= max_n; i++) {
    		if (p[i]) {
    			count++;
    			process_prime(p, max_n, i);
    		}
    	}
    	cout << endl;
    	cout << "The number of between 2 to " << max_n << " prime is :" << count << endl;
    	
    	//释放内存
    	delete[]p;
    	return 0;
    }
    
    /*
    	处理质数函数，打印传递给函数的n，然后把数组p中所有关于n的倍数的元素标记为false
    */
    void process_prime(bool *p, int max_n, int n) {
    	cout << n << "\t";
    	for (int i = n+n; i <= max_n; i += n) {
    		p[i] = false;
    	}
    }

代码原理：

首先创建一个N+1大小的bool类型的数组，为其分配内存，并且将其所有元素初始化为true；

然后从下标2开始，将下标为2的倍数的元素全设为false；

然后是下标3,。。。

如果元素为true，说明其为质数，将其下标打印，并计数。

**进阶：查找N至M之间的质数**

**思路：先查找2至M之间的质数，将大于N的质数输出即可。**

#include <iostream>
    using std::cout;
    using std::cin;
    using std::endl;
    
    //查找lower至upper之间的所有质数，返回质数的个数,包括lower和upper
    int get_prime(int upper, int lower);
    int main(void) {
    	int upper = 0,lower = 0;
    	
    	cout << "Cauculator primes up to what number? "<<endl;
    	cout << "enter upper:";
    	cin >> upper;
    	cout << "enter lower:";
    	cin >> lower;
    	int count = get_prime(upper, lower);
    	cout << "The number of between " << lower << " to " << upper << " prime is :" << count << endl;
    	return 0;
    }
    
    int get_prime(int upper, int lower) {
    
    	if (upper < 2 ) return 0;
    	int count = 0;//质数的个数
    	//分配内存
    	bool *p = new bool[upper + 1];
    
    	//初始化
    	for (int i = 2; i <= upper; i++) {
    		p[i] = true;
    	}
    	//筛选
    	for (int i = 2; i <= upper; i++) {
    		if (p[i]) {
    			for (int j = i * 2; j <= upper; j += i) {
    				p[j] = false;
    			}
    		}
    	}
    	//查找质数
    	for (int i = lower; i <= upper; i++) {
    		if (p[i]){
    			count++;
    			cout << i << "\t";
    		}
    	}
    	cout << endl;
    
    	//释放内存
    	delete[]p;
    	return count;
    }

[Link 1]: https://baike.baidu.com/item/%E8%B4%A8%E6%95%B0
[20160703235154990]: /images/20221123/68340ff70d924bce9dcda26afb3cddf4.png