关于C语言中素数的求解

什么是素数？

一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做素数。（素数=质数）

在C语言中求解素数的几种方法。

方法一：直接试数法（从1开始逐一试数）

例：求解100到200之间的素数。

#include<stdio.h>
int main()
{
	int i = 0;
	int  count = 0;
	for (i = 100; i <= 200; i++)
	{
		int j = 0;
		for (j = 2; j < i; j++)
		{
			if (i % j==0)
			{
				break;
			}
		}
		if (i == j)
		   {
			printf("%d ", i);
			count++;
		   }
		
	}
	printf("\ncount=%d\n", count);
	return 0;
}

效果如下：

此方法逻辑是从2开始到i结束逐一检验看中间是否有能够被j整除的（其中j为2到i之间的自然数）

方法二：利用中间量转换求解

例：求解100到200之间的素数。

#include<stdio.h>
int main()
{
	int i = 0;
	int  count = 0;
	
	for (i = 100; i <= 200; i++)
	{
		int j = 0;
		int num = 1;
		for (j = 2; j < i; j++)
		{

			if (i % j == 0)
			{
				num = 0;

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

效果如下：

此方法引入了num作为中间量，如果 i能整除j那么num为0就不是素数不打印i，如果 i不能整除j那么num为1就是素数打印i

方法三：利用sqrt函数开平方简便计算

例：求解100到200之间的素数。

#include<stdio.h>
#include<math.h>
int main()
{
	int i = 0;
	int  count = 0;
	
	for (i = 100; i <= 200; i++)
	{
		int j = 0;
		int num = 1;
		for (j = 2; j <= sqrt(i); j++)
		{

			if (i % j == 0)
			{
				num = 0;

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

效果如下：

此方法利用sqrt函数将i开平方用来简便计算（需要引用头文件math.h）

优化：

红色标记出可以直接跳过100到200之间的偶数从而简便运算，效果不变