算例一

• 题目描述

• 解题思路

①素数（又叫质数）：素数即只能被自身和1 整除的大于1 的正整数

②我们只需测试到不比sqrt（n）（对 n 开根号）大的整数即可，若到这个整数为止，所有正整数数均不能整除n，则可以断定， n 为素数

• 解题代码

#include <stdio.h>
#include <math.h>
bool judge(int x) { //判断一个数是否为素数
	if (x <= 1) return false; //若其小于等于1,必不是
	int bound = (int)sqrt(x) + 1; //计算枚举上界,为防止double值带来的精度损失,所以采用根号值取整后再加1, 即宁愿多枚举一个数也不能少枚举一个数
		for (int i = 2; i < bound;i++) {
			if (x % i == 0) return false; //依次枚举这些数能否整除x,若能则必不为素数
		}
	return true; //若均不能则为素数
}
int main() {
	int x;
	while (scanf("%d", &x) != EOF) {
		puts(judge(x) ? "yes" : "no"); //依据函数返回值输出答案
	}
	return 0;
}

• 注意点

①int bound = (int)sqrt(x) + 1; //宁可错杀一百，也不放过一个

②注意别把sqrt()放到for循环里，因为sqrt比较耗时，每次都执行一遍太浪费时间，同理用于strlen()

 

 

算例二

• 题目描述

• 解题思路

①若一个数不是素数，则必存在一个小于它的素数为其的因数

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

• 解题代码

#include <stdio.h>
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 <= 10000;j += i) { //并将该数的所有倍数均标记成非素数
				mark[j] = true;
		}
	}
}
int main() {
	init(); //在程序一开始首先取得2到10000中所有素数
	int n;
	while (scanf("%d", &n) != EOF) {
		bool isOutput = false; //表示是否输出了符合条件的数字
		for (int i = 0; i < primeSize;i++) { //依次遍历得到的所有素数
			if (prime[i] < n && prime[i] % 10 == 1) { //测试当前素数是否符合条件
					if (isOutput == false) { //若当前输出为第一个输出的数字,则标记已经输出了符合条件的数字, 且该数字前不输出空格
							isOutput = true;
						printf("%d", prime[i]);
					}
					else printf(" %d", prime[i]); //否则在输出这个数字前输出一个空格
			}
		}
		if (isOutput == false) { //若始终不存在符合条件的数字
			printf("-1\n"); //输出-1并换行
		}
		else printf("\n"); //换行
	}
	return 0;
}

• 注意点

①这道题中重要的一点就是如何减少遍历次数，所以采取了一些小技巧：

（i）在标记倍数的时候，并没有从2*i开始，而是从i*i开始，因为i*k（k<i）必已经在求k的某个素因数的时候就标记过了

（ii）在测试当前素数是否符合条件的时候，用prime[i]<n条件先卡一卡，排除掉一些情况