【C 语言】如何判断素数

距离上次更新本文已经过去了 694 天，文章部分内容可能已经过时，请注意甄别

如何判断素数

题目要求：输出 100-200 的素数

首先我们要知道什么是素数（质数），以防有人忘记（比如刚学开始学 c 的我就忘记了）

素数（质数）只能被 1 和它自己整除

7 只能被 1 和 7 整除，是素数
9 能被 3 整除，不是素数

方法 1— 试除法

#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)//i可以整除j，i不是素数
             {
                 break;
             }
        }
        if(j==i)//i只能整除它自己，是素数
        {
            count++;
            printf("%d ",i);
        }
    }
    printf("\ncount=%d\n",count);//计算100-200之间有几个素数
    return 0;
}

这个代码比较死，只是输出了 100 到 200 之间的素数，完成了题目的要求

我们可以把它改造成输入一个数字，判断是否是素数的形式

代码改造 1-1

用户输入一个数字
代码判断是否为素数
是，输出 “是素数” 以及用户输入的值
不是，输出 “不是素数”

#include<stdio.h>

int main()
{
    int i=0;
    int j=0;
    scanf("%d",&i);
    for(j=2;j<i;j++)
    {
    	if(i%j==0)
        {
            printf("不是素数\n");
            break;
    	}
	}
    if(j==i)
    {
        printf("是素数,i=%d\n",i);
    }      
}

结果如下：

上面的这串代码能很好地完成我们的需求，但它还有优化的空间

方法 2— 开平方法

方法 1 中的 for 循环为 j<i

如果数字很大的话，要循环非常多次才能出现 j==i 的情况

这就拖慢了我们程序运行的速度

这里我们引入一个概念

若 i=a*b
a 和 b 中至少有一个数字 <= 开平方 i

如 16=2x8=4x4
其中 2<4

这样就能得到一个结论：

在根号 i 之前一定有一个数字 n 是非素数的除数

如果找不到这个数字 n，说明该数字为质数

利用开平方法，我们可以将需要查找的数字范围缩小很多

以下是用该方法完成开头题目要求的代码示例

#include<stdio.h>

int main()
{
	int i=0;
	for(i=101;i<=200;i+=2)
	{
		int j=0;
		for(j=2;j<=sqrt(i);j++)
		{
			if(i%j==0)
			{
				break;
             }
		}
		if(j>sqrt(i))
		{
			printf("%d ",i);
		}
	}
	return 0;
}