素数求解的N种境界

本期介绍

主要介绍：如何快速筛查素数的方法，详细讲解了试除法和筛选法的N种境界。

---

目录

• 前言
• 试除法
  • 境界1（试除从 2—(n-1) ）
  • 境界2（排除2的倍数的合数）
  • 境界3（试除从 2—sprt(n) ）
• 筛选法
  • 境界1（基础）
  • 境界2（优化）
• 总结

---

前言

  质数（prime number）又称素数。一个大于1的自然数，除了1和它本身外，不能被其他自然数整除的数被称为素数（换句话说就是该数除了1和它本身以外不再有其他的因数）。现在有一个题目：请编写代码找出1——120之间的素数。那我们该如何编写关于这道题的较优代码呢？下面我会介绍两种类型的算法的代码，第一种为“试除法”，第二种为“筛选法”。

---

试除法

  那什么是试除法呢？通过不断试除1和本身之外的自然数来判断该数是否为素数的方法称为试除法（只要有一个自然是能够整除该数，则其就不是素数；若一个都不能整除该数，则其就是素数）。

境界1（试除从 2—(n-1) ）

  该方法就是循环遍历所有情况，效率很差。

#include<stdio.h>
int main()
{
    
	int i = 0;
	int count1 = 0;//循环的次数
	int count2 = 0;//素数的个数
	printf("1——120之间素数为：\n");
	for (i = 2; i <= 120; i++)
	{
    
		int j = 0;
		for (j = 2; j < i; j++)//试除除了1和它本身之外所有的数
		{
    
			count1++;
			if (i % j == 0)
			{
    
				break;
			}
		}
		if (j >= i)//若一个试除数都无法整除该数，则说明该数为素数
		{
    
			printf("%d ", i);
			count2++;
		}
	}
	printf("\n循环的次数为：%d", count1);
	printf("\n素数的个数为：%d",count2);
	return 0;
}

---

境界2（排除2的倍数的合数）

  该方法还是和境界1一样是通过循环遍历所有情况达到目的地，其本质并没有发生任何变化，仅仅是稍微优化了一下下，几乎可以说是可有可无，所以该程序执行效率仍然差。

#include<stdio.h>
int main()
{
    
	int i = 0;
	int count1 = 0;//循环的次数
	int count2 = 0;//素数的个数
	printf("1——120之间素数为：\n");
	printf("%d ", 2);//不能忘记2也是素数
	count2++;
	for (i = 3; i <= 120; i+=2)//省略掉2的倍数的合数
	{
    
		int j = 0;
		for (j = 2; j < i; j++)//试除除了1和它本身之外所有的数
		{
    
			count1++;
			if (i % j == 0)
			{
    
				break;
			}
		}
		if (j >= i)//若一个试除数都无法整除该数，则说明该数为素数
		{
    
			printf("%d ", i);
			count2++;
		}
	}
	printf("\n循环的次数为：%d", count1);
	printf("\n素数的个数为：%d",count2);
}

---

境界3（试除从 2—sprt(n) ）

  该方法是通过试除从 2—sprt(n) 之间的所有数来判断是否为素数的，那为什么是 2—sprt(n) 这个范围呢？因为若这个数它不是素数必然可以进行因式分解，分解成两个因数相乘；既然这两个因数都可以用来判断是否为素数，那我们为什么要判断它两遍呢，一遍不就足够了？那该如何实现呢？
  如果你多因式分解几组自然数，你会发现分解出来的两个因数必然是一大一小且都相互趋近于被分解的那个数n的算数平方根。所以我们发现第1个因数的范围必然是在 2——sprt(n) 之间，而又由于我们只需要知道其中的一个因数就可以判断是否为素数，故试除的范围就可以定在 2——sprt(n) 之间了，这样我们就可以省略 sprt(n)——(n-1) 之间的试除，这真的是大大优化了境界1时的代码呀！！！

#include<stdio.h>
#include<math.h>
int main()
{
    
	int i = 0;
	int count1 = 0;//循环的次数
	int count2 = 0;//素数的个数
	printf("1——120之间素数为：\n");
	for (i = 2; i <= 120; i++)
	{
    
		int j = 0;
		for (j = 2; j <= sqrt(i); j++)//试除除了2——sqrt（i）之间的数
		{
    
			count1++;
			if (i % j == 0)
			{
    
				break;
			}
		}
		if (j > sqrt(i))//若一个试除数都无法整除该数，则说明该数为素数
		{
    
			printf("%d ", i);
			count2++;
		}
	}
	printf("\n循环的次数为：%d", count1);
	printf("\n素数的个数为：%d", count2);
}

---

筛选法

  筛选法的由来可以追溯到古希腊时期，那时有个人叫埃拉托斯特尼，他发现可以通过在涂蜡的木板记下数字，接着在蜡上以记一个点来作为删去一个数字，然后从最小的质数开始一个接着一个的划掉这些质数的倍数的方法来实现求质数（最后那些没被点标记的数就是质数了）。质数查找完成后，这有着密密麻麻小点的涂蜡板看上去就像一个筛子，所以就把着这种方法叫做：“埃拉托斯特尼筛选”，简称：筛选法。
  从上面我们可以看出筛选法和试除法其实有着本质上的区别，试除法是判断每一个数是不是素数来达到目的；而筛选法不是如此，筛选法是将不是素数的数全部去除，然后得到余下的数来达到目的。那该如何实现这个代码呢？看下去。

境界1（基础）

  首先1不是质数也不是合数，所以要划去；接着2是公认最小的质数，所以要保留下来，再把所有2的倍数去掉；然后接下来遇到的第一数不会是2的倍数，所以它必然只可能被1和他自身整除，为素数，而2后面第一个没有被划去的数是3，所以要保留素数3，再把所有3的倍数去掉；接着往复之前的判断，剩下的那些大于3的数里面，最小的是5，所以5也是质数……
  上述过程不断重复，就可以把某个范围内的合数全都除去（就像被筛子筛掉一样），剩下的就是质数了。如果理解还不怎么清晰，我这有幅动图其能够直观地体现出筛法的工作过程，如下所示：

#include<stdio.h>
#include<stdbool.h>
#define NUM 200
int main()
{
    
	//建立一个bool类型的数组，用来存放该数组下标所对应的数是否为素数；是素数则存储true，否则存储false。
	bool is_prime[NUM] = {
     0 };
	int i = 0;
	int count1 = 0;//循环总次数
	int count2 = 0;//素数的个数
	//初始化bool数组
	for (i = 0; i < NUM; i++)
	{
    
		is_prime[i] = true;
	}
	printf("1——120之间素数为：\n");
	//排查掉不是素数的数，并输出素数
	for (i = 2; i <= 120; i++)
	{
    
		if (is_prime[i])
		{
    
			int j = 0;
			count2++;
			printf("%d ", i);
			for (j = i + i; j <= 120; j += i)//从i+i开始筛i的倍数
			{
    
				is_prime[j] = false;
				count1++;
			}
		}
	}
	printf("\n循环总次数：%d", count1);
	printf("\n素数的个数：%d", count2);
	return 0;
}

---

境界2（优化）

  其实上面这个程序还可以优化一下，不知道你有没有发现有一些数字我们会重复筛查好多次。就譬如数字6，我在筛查2的倍数时已经把它筛了一次，可在筛查3的倍数时仍然会重复筛，但其实筛一次就够了。所以只要我们能实现每个数只筛一次，就能节约一定的时间，这样程序就可以得到优化。
  那该如何做呢？我们发现，当 i=2 时，我们只需从 2 * 2 = 4 开始筛2的倍数；当 i=3 时，其实我们只需从3 * 3 = 9开始筛3的倍数（优化前的代码是从3+3开始筛的，因为前面我已经把2的倍数都筛了一遍，3+3自然也被筛了，所以没有必要再筛一次，那就往后看嘛从 3+3+3 开始筛）；当 i=5时 ，我们发现只有当 5+5+5+5+5 的时候（即：5 * 5 = 25）才没有被之前的数筛过，所以从这开始筛5的倍数。总结一下，在筛一个数的倍数时，只要在该数的二次方那里开始筛它的倍数即可实现每个数只筛一次。

#include<stdio.h>
#include<stdbool.h>
#define NUM 200
int main()
{
    
	//建立一个bool类型的数组，用来存放该数组下标所对应的数是否为素数；是素数则存储true，否则存储false。
	bool is_prime[NUM] = {
     0 };
	int i = 0;
	int count1 = 0;//循环总次数
	int count2 = 0;//素数的个数
	//初始化bool数组
	for (i = 0; i < NUM; i++)
	{
    
		is_prime[i] = true;
	}
	printf("1——120之间素数为：\n");
	//排查掉不是素数的数，并输出素数
	for (i = 2; i <= 120; i++)
	{
    
		if (is_prime[i])
		{
    
			int j = 0;
			count2++;
			printf("%d ", i);
			for (j = i * i; j <= 120; j += i)//从i*i开始筛i的倍数
			{
    
				is_prime[j] = false;
				count1++;
			}
		}
	}
	printf("\n循环总次数：%d", count1);
	printf("\n素数的个数：%d", count2);
	return 0;
}

---

总结

  你别看试除法的境界3的循环次数和筛选法的循环次数也就差一半，就认为筛选法的效率也就比试除法快一倍。若我们把求素数的范围提到1000以内，筛选法的循环次数为：128，而试除法的执行次数却是：5228。所以从这可以看出，求素数的范围越大就越能体现试除法的优越性。上面这些就是我今天想向大家分享的素数求解的N种境界！

---

这份博客如果对你有帮助，给博主一个免费的点赞以示鼓励欢迎各位点赞评论收藏️，谢谢！！！
如果有什么疑问或不同的见解，欢迎评论区留言欧。