方法① 2~m-1范围
整体思路就是,整数取余==0就break,后续判断取余不为0的i次数,如果到头也就是i值溢出m-1 也就是最后一次循环i++都没break,说明全部取余都不为0,贼为素数
尽头 i<=m-1 等于号和-1可以抵消, 等于号去掉,-1去掉,i<m 取不到m 也相当于取到m-1
代码
int i;
int m = 419;
for ( i = 2; i <= m-1; i++)
{
if (m%i==0)
{
break;
}
}
if (i>m-1)
{
printf("是%d", m);
}
else
{
printf("不是%d", m);
}
方法② 2~m/2范围
时间复杂度优化
将到自身-1的范围缩小为了 到自身的二分之一,减少了其余判断,下面的成功次数要大于m/2,因为m/2取得到而最后一次除数取余判断后会自增到m/2 +1.所以要大于m/2
代码
int i;
int m = 121;
for (i = 2; i <= m / 2; i++)
{
if (m % i == 0)
{
break;
}
}
if (i > m / 2)
{
printf("是%d", m);
}
else
{
printf("不是%d", m);
}
方法③ 2~根号m范围
将范围再次缩小为根号n,因为如果能被小因子或是相同因子 整除那么其余就不判断
代码
int i, k;
int num = 9;
k = sqrt(num);
for (i = 2; i <= k; i++)
{
if (num % i == 0)
{
break;
}
}
if (i > k)
{
printf("是%d\n", num);
}
else
{
printf("不是%d", num);
}
方法④,判断100~200间的所有素数
将输入值n转为for循环展开的所有数字 ,然后多次执行素数判断
int i,k,n;
for ( n = 100; n < 200; n++)
{
k = sqrt(n);
for (i = 2; i <= k; i++)
{
if (n % i == 0)
{
break;
}
}
if (i > k)
{
printf("是%d\n", n);
}
}
这里还可以改进,偶数不可能为素数,因此我们每次循环结束 n加2
int i,k,n;
for ( n = 101; n < 200; n=n+2)
{
k = sqrt(n);
for (i = 2; i <= k; i++)
{
if (n % i == 0)
{
break;
}
}
if (i > k)
{
printf("是%d\n", n);
}
}