素数的求解精析！！_c语言j*j<=i和开sqrt(i)有啥区别

素数：只能被1和本身整除的数称为素数。

方法一：试除法

假设要看100是否为素数，只需要将100分别与2~99 的所有数依次相除。

如果2~99其中有数字能够被100整除，则说明100不是素数；

如果2~99中没有数字能够被100整除，则说明100是素数。

即要看i是否为素数，只需要将i分别与2~i-1的所有数一次相除。

因此需要用到循环，,定义一个新的变量j，使j的范围在2~i-1之间，考虑到j从2开始，即起始位置为j=2，终止位置为i-1,即循环条件为j<=i-1,因为要将i与2~i-1的数分别相除，所以每次循环后i增加1，即控制条件为j++。

综上，应使用for循环。>>for (j = 2; j < =i - 1; j++)

//假设我们要打印100-200之间的素数 

#include <stdio.h>
int main()
{
	int i = 0;
	for (i = 100; i <= 200; i++)//控制i的范围在100-200之间
	{
		int j = 0;
		int flag = 1;//flag=1,假设i是素数
		for (j = 2; j <= i - 1; j++)//用2~i-1之间的数试除
		{
			if (i % j == 0)//说明j能够整除i,即2~i-1之间有数能够整除i，说明i不是素数
			{
				flag = 0;//说明i不是素数
				break;//这时因为i不是素数了，即已经在2~i-1之间找到数能够整除i，找到一个就可以说明 
                      //i不是素数了，因此不用继续判断是否接下来还会有数整除i，因此可以提前结束循 
                      //环，故break跳出循环
			}
		}
		if (flag == 1)//上一步跳出循环只是跳出了内部循环，即只是判断了100~200之间的其中一个数字 
                      //不是素数，但除此之外还有其他数字需要判断，在这些判断后的结果中有是素数 
                      //的，有不是素数的，因此还需要加以判断，从中筛选出是素数的部分
			printf("%d ", i);//打印素数
	}
	return 0;
}

方法二：改进试除法（缩小试除的范围）

假设m不是素数，m=a*b,则a和b中至少会有一个数小于等于${\color{Red} {\color{Red} }}\sqrt{m}$

例如：18=2*9--------2<$\large {\color{Red} ^{\sqrt{18}}}$

因此可以缩小内层for循环的范围,即for(j=2;j<=sqrt(i);j++)

注：sqrt(i)为一个开平方的库函数，使用时需要引用头文件#include<math.h>

则改进后的代码为：

#include <stdio.h>
#include <math.h>
int main()
{
	int i = 0;
	
	for (i = 100; i <= 200; i++)
	{
		int j = 0;
		int flag = 1;
		for (j = 2; j <=sqrt(i); j++)//改进
		{
			if (i % j == 0)
			{
				flag = 0;
				break;
			}
		}
		if (flag == 1)
			printf("%d ", i);
	}
	return 0;
}

方法三：改进素数查找的循环范围

因为是素数，所以第一个数一定不能是偶数，因此从101开始，而两个素数之间至少差1,且所以可以改进外层for循环的控制条件，即将i++改成i+=2;

即for(i=101；i<=sqrt(i);i+=2)

#include <stdio.h>
#include <math.h>
int main()
{
	int i = 0;
	
	for (i = 101; i <= 200; i+=2)//改进
	{
		int j = 0;
		int flag = 1;
		for (j = 2; j <=sqrt(i); j++)
		{
			if (i % j == 0)
			{
				flag = 0;
				break;
			}
		}
		if (flag == 1)
			printf("%d ", i);
	}
	return 0;
}