素数求解的学习1

序

素数即质数，它在自然数里的分布是不规律的，但是其在数学研究上占有重要地位。因此对于素数的求解法方法不断被人们优化着。在C语言中求解素数也是非常经典的一道题目，以下简单记录 我学习求解素数的收获。

素数的暴力求解

对与如同我这的初学者，首先学习以素数的基本概念求解素数，先写一个代码判断一个数是否为素数：因为素数只能被1和它本身整除，对于一个数字 num 用2到 num-1 的整数试除 num，如果都不能整除，则 num 为素数，否则不是素数，以下为代码的实现。

#include <stdio.h>
int main()
{
	int flag = 1; //假定num为素数 
	int num = 0;
	scanf("%d", &num);
	for (int i = 2; i < num; i++)
	{
		
		if (num % i == 0)
		{
			printf("不是素数\n");
			flag = 0; //如果走到这一步，num不是素数
			break;
		}

	}
	if (flag == 1)
		printf("是素数");
	return 0;
}

这里我们用到了 for 循环对2到 num-1 的数进行了试除，以 flag 作为标记判断 num 是否被整除。若 num 被整除就打印"不是素数"，flag 的值被改写为0，然后跳出循环，程序执行完成；

若循环至 i=num ，num 也未被整除，则flag未被改写，打印"是素数"。

这样的方法是判断素数最粗浅的方法，如果求12是否为素数，这里需要进行十次循环，而2就已经能够整除12了，根本不需要后面的运算。如果需要判断的数字越大越多，则会需要进行更多次的循环，无疑会降低计算机的运行效率。 我们试着用这个方法求解101到200的素数，并计算循环的次数，用作后面的对比。

#include <stdio.h>
int main()
{
	int count = 0; //计算内循环次数
	int flag;
	int i = 0;
	for (i = 101; i <= 200; i++)
	{
		
		int j = 0;
		for (j = 2; j < i; j++)
		{
			count++;
			flag = 0;

			if (i % j == 0)
			{
				break;
			}

			flag = 1;
		}
		if (flag == 1)
		{
			printf("%d ", i);
		}
	}
	printf("\n");
	printf("%d", count);
    return 0;
}

可以看到计算内循环进行了3291次。

试着缩小试除数字的范围1

一.

我们可以轻易判断除2以外素数不可能为偶数，而对于一个数x，如果有（除了自身以外的）质因数，那肯定会小于等于 x/2。以此简单修改代码外循环中的调整部分和内循环中的判断部分。

#include <stdio.h>
int main()
{
	int count = 0;
	int flag;
	int i = 0;
	for (i = 101; i <= 200; i+=2) //i++改为i+=2
	{
		
		int j = 0;
		for (j = 2; j < i/2; j++) //j<i改为j<i/2
		{
			count++;
			flag = 0;

			if (i % j == 0)
			{
				break;
			}

			flag = 1;
		}
		if (flag == 1)
		{
			printf("%d ", i);
		}
	}
	printf("\n");
	printf("%d", count);
    return 0;
}

对于这次修改外循环次数将近减半，内循环亦然，总体效率提升不算明显。

二.

调动我们的数学知识，因为因数都是成对出现的，如：对于100，可以写成 5 * 20，10 * 10，4 * 25。观察我们可以发现，对于一个数x，如果有（除了自身以外的）质因数，那么它的一个因数必然小于等于它的开平方数√ x。

#include <stdio.h>
#include <math.h> //调用sqrt()引用头文件
int main()
{
	int count = 0;
	int flag;
	int i = 0;
	for (i = 101; i <= 200; i+=2)
	{
		
		int j = 0;
		for (j = 2; j < sqrt(i) ; j++) //将j<i/2改为j<sqrt(i)
		{
			count++;
			flag = 0;

			if (i % j == 0)
			{
				break;
			}

			flag = 1;
		}
		if (flag == 1)
		{
			printf("%d ", i);
		}
	}
	printf("\n");
	printf("%d", count);
	return 0;
}

这时候发现内循环指进行了340，这无疑提高了很多效率。

试着缩小试除数字的范围2

前面提到了除2的偶数都不可能为素数，也可以理解为2的倍数不可能为素数，以此将其排除。以此借鉴筛选法的思路，可以简单改良代码。个位数中2，3，5，7为素数，那么他们的倍数不可能为素数，进一步排除了非素数。

我们可以写一个数组将101到200的数放入，筛出2，3，5，7的倍数，将其赋值为为0，再建立一个数值接收其余数字。结合上面的方法，效率可以在一步提升。代码的实现下一张博客给出。