判断一个数是不是素数，素数为什么到平方根就可以了_素数平方根判断

判断一个数是不是素数：

素数的判断标准是：大于1的自然数中，除了1和它本身以外不再有其他因数的自然数
判断一个数是否为素数，就只需要从：[2，该数-1]区间中的整数与作为除数去和这个判断数相除，看看区间中有无可以整除这个判断数的数字，有就不符合标准，即——不为素数

求素数为什么到平方根就可以了？

若要判断x是否为素数， 只需判断1-根号x中是否有它的因子即可

举个栗子：
n=36 36的平方是6 36=1*36= 2*18= 3*12= 4*9= 6*6 
{1，2，3，4，6}<=判数平方根6 ；{36，18，12，9，6}>=判数平方根6
因此，我们只需判断1-6中是否有36的因子。 如果没有，那么大于6的数中，也不会有36的因子。
1
2
3
4

题目描述

1、编写一个函数用来测试带入的数字是否为素数，函数的格式为：(最底层的函数)

int IsPrime(int n)

当带入n的数字是素数时，返回值是1，否则返回值是0；
再main函数中调用IsPrime函数进行测试，连续输入3个数字，判断这个3个数字分别是否为素数并打印；

2、编写一个函数打印出从x到y之间的素数：(中层函数)

void PrintPrime(int x,int y);

在PrintPrime中循环调用IsPrime函数实现;
在main函数输入2个不同的数字传给PrintPrime的x和y参数;

3、编写一个函数打印出从x之后n个的素数：(中层函数)

void PrintPS(int x,int n);

要求PrintPS循环调用IsPrime函数实现，在main函数输入2个数字传递PrintPS的x和n参数;

---

示例代码：

#include <stdio.h>
#include <math.h>
//第一次优化：n /2
//第二次优化：sqrt(n) 请思考：你敢用平方根来作为循环条件吗，为什么？
// //C++ 有bool 就是用int 1代表是（true），0代表不是（false）
//判断带入的n内的数值是不是素数
int IsPrime(int n) //判断一个数是不是素数？
{
	int m = (int)sqrt(n) + 1;

	for (int i = 2; i < m; ++i)
	{
		if (n % i == 0)
			return 0;
	}
	return 1;
}
void PrintPrime(int x, int y) //求x到y之间有多少个素数，全部打印
{
	int sum = 0;
	for (int i = x; i < y; ++i)
	{
		if (IsPrime(i))
		{
			printf("%d ", i);
				++sum;
		}
		
	}
	printf("从%d到%d总共有%d个素数\n", x, y, sum);
}

void PrintPS(int x, int n) //求x之后n个素数，全部打印
{
	printf("\n%d之后%d个素数\n", x, n);
	while (n)
	{
		if (IsPrime(x))
		{
			printf("%d ", x);
			n--;
		}
		++x;
	}
}
int main()
{

	IsPrime(7);

	PrintPrime(300, 529);
	PrintPrime(25, 390);


	PrintPS(91, 20);
	PrintPS(300, 100);	
	PrintPS(100, 150);

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60