初识C语言==＞如何判断一个数字是否为素数（质数）？

• 如何判断素数
• • 方法1---试除法
  • 代码改造1-1
  • 方法2---开平方法
• 感谢你看到最后

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

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

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

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

#include

int main()
{
    int i=0;
    int count=0;
    for(i=100;i<=200;i++)
    {
        int j=0;
        for(j=2;j 
 
这个代码比较死，只是输出了100到200之间的素数，完成了题目的要求
 
我们可以把它改造成输入一个数字，判断是否是素数的形式
 
 
代码改造1-1 
用户输入一个数字
代码判断是否为素数
是，输出“是素数”以及用户输入的值
不是，输出“不是素数”
 
#include

int main()
{
    int i=0;
    int j=0;
    scanf("%d",&i);
    for(j=2;j 
结果如下：
 
 
 
 
上面的这串代码能很好地完成我们的需求，但它还有优化的空间
 
方法2—开平方法 
方法1中的for循环为j 
如果数字很大的话，要循环非常多次才能出现j==i的情况
 
这就拖慢了我们程序运行的速度
 
这里我们引入一个概念
 
若i=a*b
a和b中至少有一个数字 <= 开平方i
 
 
 
如16=2x8=4x4
 
 
其中2<4
 
 
这样就能得到一个结论：
 
在根号i之前一定有一个数字n是非素数的除数
 
如果找不到这个数字n，说明该数字为质数
 
 
利用开平方法，我们可以将需要查找的数字范围缩小很多
 
以下是用该方法完成开头题目要求的代码示例
 
#include

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;
}
 
 
将这个代码改造成1-1那种形式也不难，自己试试吧！
 
 
感谢你看到最后 
如果这篇博客对你有帮助，请点赞支持一下，万分感谢！