王道计算机机试——巧妙求素数素数筛法

Thadea ·

更新时间:2024-09-20

· 869 次阅读

王道计算机机试——巧妙求素数素数筛法 题目描述：

输入一个整数 n(2<=n<=10000)，要求输出所有从 1 到这个整数之间 (不包括 1 和这个整数 )个位为 1 的素数，如果没有则输出 -1。
输入：输入有多组数据。每组一行，输入 n。
输出：输出所有从 1 到这个整数之间 (不包括 1 和这个整数 )个位为 1 的素数 (素数之间用空格隔开，最后一个素数后面没有空格 )，如果没有则输出 -1。
样例输入：
100
样例输出：
11 31 41 61 71
来源： 2008 年北京航空航天大学计算机研究生机试真题

巧妙求素数思路

若一个数不是素数，则必存在一个小于它的素数为其的因数。这个命题的正确性是显而易见的。那么，假如我们已经获得了小于一个数的所有素数，我们只需确定该数不能被这些素数整除，这个数即为素数。但是这样的做法似乎依然需要大量的枚举测试工作。
正因为如此，我们可以换一个角度，在我们获得一个素数时，即将它的所有倍数均标记成非素数，这样当我们遍历到一个数时，它没有被任何小于它的素数标记为非素数，则我们确定其为素数。

解题步骤

我们按照如下步骤完成工作：
从 2 开始遍历 2 到 1000000 的所有整数，若当前整数没有因为它是某个小于其的素数的倍数而被标记成非素数，则判定其为素数，并标记它所有的倍数为非素数。然后继续遍历下一个数，直到遍历完 2 到 1000000 区间内所有的整数。此时，所有没被标记成非素数的数字即为我们要求的素数。这种算法被我们称为素数筛法。

代码

#include
using namespace std;
int prime[10000];//保存筛得的素数
int primeSize;//保存素数的个数
bool mark[10001];//若mark[x]为true，则表示该数x已经被标为非素数
void init() {//素数筛法
	for (int i = 1; i <= 10000; i++) {
		mark[i] = false;
	}//初始化，所有数字均没被标记
	primeSize = 0;//得到的素数个数为0
	for (int i = 2; i < 10000; i++) {//依次遍历2到10000所有数字
		if (mark[i] == true) continue;//若该数字已经被标记过，则跳过
		prime[primeSize++] = i;//否则又得到一个新素数
		for (int j = i * i; j > n) {
		bool isOutput = false;//判断是否输出了符合条件的数字
		for (int i = 0; i < primeSize; i++) {//依次遍历得到的所有素数
			if (prime[i] < n && prime[i] % 10 == 1) {//测试当前素数是否符合条件
				if (isOutput == false) {//若当前输出为第一个输出的数字，则标记已经输出了
					//符合条件的数字，且该数字前不输出空格
					isOutput = true;
					cout << prime[i];
				}
				else cout << ' ' << prime[i];//否则在输出这个数字前输出一个空格
			}
		}
		if (isOutput == false) {//若始终不存在符合条件的数字
			cout << '无';
		}
		else cout << endl;
	}
	return 0;
}

作者：xyzxyzxyz1999

素数

1024 个赞