C语言练习---【求素数】（一篇带你掌握素数求解）

🦖作者：学写代码的恐龙
🦖博客主页：学写代码的恐龙博客主页
🦖专栏：【初级c语言】
🦖语录：❀未来的你，一定会感谢现在努力奋斗的自己❀

🦖：什么是素数？

素数又叫质数。素数，指的是“大于1的整数中，只能被1和这个数本身整除的数”。

🦖：求解思路

知道了什么是素数之后，我们就可以根据素数的特点来判断一个数是否为素数。既然素数只能被1和这个数本身整除，那要判断n是否为素数，我们就可以拿2~n-1的每一个整数去试除n，看余数是否为0，如果余数为0，说明n被整除，则n不是素数。如果2-n-1的所有整数去试除n余数都不为0，则说明n是素数。通过分析不难发现，要取到2-n-1的每一个整数，我们需要写一个循环。判断余数是否为0，需要用到求余符号’%'。知道了这些我们就可以来写代码了

🦖：求100-200的所有素数（代码实现）

#include 
int main()
{
	int i = 0;
	int j = 0;
	
	for (i = 100; i <= 200; i++)
	{
		//判断i是否为素数
		int chag = 1;//假设是素数，注意chag的定义一定是在这里
		for (j = 2; j <=i-1; j++)//利用这个循环依次取到2-i-1的所有整数
		{
			if (i % j == 0)
			{
				chag=0;//如果i % j！=0说明果不是素数，让chag=0，此时i是否为素数判断完毕，可以终止这个循环，判断下一个数字是否为素数
				break;
			}
		}
		if (chag == 1)//如果i是素数，则程序不会进入上面的if语句，就不会执行chag=0;这条语句，所以chag的值还是最初假设的1，因此我们可以通过这里chag的值来判断i是否为素数
		{
			printf("%d ", i);
		}
	}
	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

对chag的理解：

代码里定义了一个chag让它赋初值为1，并且假设i是素数，如果当程序判断出i不是素数，重新把0赋值给chag，最终我们可以通过chag的值来看出i是否是素数。这里需要特别注意定义chag的位置，必须是在上面代码中的位置进行chag的定义。判断一个数是否为素数之前我们都先假设这个数就是素数，让chag=1;如果chag的定义不在这里，如果判断i不是素数，不是素数的话chag已经被重新赋值为0，如果chag的定义不在这里，那当判断第i+1个数是否为素数的时候chag最初的值就是0，这就会影响我们后面的判断，会导致判断结果出错。

🦖：程序优化

先给大家举个例子：我们都知道2×8=16。这说明16可以被2整除，也可以被8整除，被2整除得8，被8整除得2。因此当我们判断出2可以整除16以后，就无需再判断8是否可以整除16，因为通过数学知识，我们可以直接确定8一定能整除16。还有哪两个数相乘等于16呢？除了2×8=16以外，还有4×4=16。我们不难发现，当a×b=c的时候，a和b中一定有一个数字小于等于根号c，且当我们判断出a可以整除c以后，那b一定可以整除c。因此我们只需要判断2~根号c的所有整数是否可以整除c就可以，如果都不能整除说明c就是素数。反之c不是素数。

#include 
#include 
int main()
{
	int i = 0;
	int j = 0;
	
	for (i = 100; i <= 200; i++)
	{
		//判断i是否为素数
		int chag = 1;//假设是素数
		for (j = 2; j <=sqrt(i); j++)//利用这个循环依次取到2-根号i的所有整数
		{
			if (i % j == 0)
			{
				chag=0;//如i % j！=0说明果不是素数，让chag=0，此时i是否为素数判断完毕，可以终止这个循环，判断下一个数字是否为素数
				break;
			}
		}
		if (chag == 1)
		{
			printf("%d ", i);
		}
	}
	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

🦖：程序进一步优化

我们很容易发现除了2，其他的偶数一定不是素数（至少可以被2整除）。素数只能是2或者奇数，但并不是所有的奇数都素数，因此我们只需要判断奇数是否是素数，无需对偶数进行判断（因为偶数一定不是素数），这可以大大帮助我们缩小判断范围。

因此求100-200的素数，我们可以从101开始判断，并且每次+2，101判断完以后判断103，然后判断105……直到199。这一下就把我们的判断范围缩小了一半。（注意：一定要从奇数开始判断，如果从偶数开始，那每次+2后得到的还是偶数，而除了2所有的偶数都不是素数。）

#include 
#include 
int main()
{
	int i = 0;
	int j = 0;

	for (i = 101; i <= 200; i+=2)//从101开始判断100-200之间所有的奇数是否是素数
	{
		//判断i是否为素数
		int chag = 1;//假设是素数
		for (j = 2; j <= sqrt(i); j++)//利用这个循环依次取到2-i-1的所有整数
		{
			if (i % j == 0)
			{
				chag = 0;//如i % j！=0说明果不是素数，让chag=0，此时i是否为素数判断完毕，可以终止这个循环，判断下一个数字是否为素数
				break;
			}
		}
		if (chag == 1)
		{
			printf("%d ", i);
		}
	}
	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

到这里，如何求解素数就讲解完了，，喜欢的话可以点赞、评论和收藏哟!