用函数实现判断素数（以及改进思路）_函数训练之素数判断(预处理篇)

素数：

在写判断素数这段代码之前，我们首先要了解一个概念什么是素数？

素数，一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数。（规定1既不是质数也不是合数）。

---

方法一：

通过概念，我们可以得到一些思路：

1.如果输入数字等于1或者小于1，不是素数

2.如果输入数字可以被2到它本身减1整除，不是素数。

代码：

int IsPrime(int n){
	if (n == 1 || n <1){      //输入数字<1或者=1，不是素数
		return 0;
	}
	for (int i = 2; i < n; i++){
		if (n%i == 0){   //输入数字可以被2到它本身减1整除，不是素数
			return 0;
		}
	}
		return 1;        //输入数字是素数
}

下面我们在主函数中调用IsPrime函数，输出100-200之间的素数。

代码：

#include <stdio.h>
int IsPrime(int n){
	if (n == 1 || n <1){ //输入数字<1或者=1，不是素数
		return 0;
	}
	for (int i = 2; i < n; i++){
		if (n%i == 0){//输入数字可以被2到它本身整除，不是素数
			return 0;
		}
	}
	return 1;//输入数字是素数
}
int main()
{
	int num = 0;
	for (num = 100; num <= 200; num++){
		if (IsPrime(num) == 1){
			printf("%d ", num);
		}
	}
	system("pause");
	return 0;
 
}

结果：

---

方法二（改进）：

判断方法还可以简化。n不必被 2~n-1之间的每一个整数去除，只需被 2 ~ √n之间的每一个整数去除就可以了。如果 n不能被 2 ~ √n间任一整数整除，n必定是素数。

原因：因为如果 n 能被 2 ~ n-1 之间任一整数整除，其二个因子必定有一个小于或等于√n ，另一个大于或等于 √n。

代码：

#include <stdio.h>
#include<math.h>
#include<stdlib.h>
int IsPrime(int n){
	if (n == 1 || n <1){ 
		return 0;
	}
	for (int i = 2; i < sqrt(n*1.0); i++){
		if (n%i == 0){
			return 0;
		}
	}
	return 1;
}
int main()
{
	int num = 0;
	for (num = 100; num <= 200; num++){
		if (IsPrime(num) == 1){
			printf("%d ", num);
		}
	}
	system("pause");
	return 0;
 
}

结果：

---

注意：

如果代码中输入的是sqrt(n)运行后可能会出现如下问题：

因为在C++中sqrt有三种类型，参数分别为long double，float，double。n定义的参数类型是int型，而sqrt()中应该试用double型或者float型，编译器不知道我们要使用哪一个sqrt类型。因此，我们要将sqrt(n)修改为sqrt（n*1.0）。