求解100~200之间的素数
对于很多人对求解素数存在一定的困惑,在这里,我将用一些方法为大家讲解我的理解,希望可以帮助大家。下面是求解100~200之间素数的方法在这个题目中,我们需要了解质数的定义,明白判断条件,结束条件是什么。求赞,求关注呀!httpshttpshttpshttps。...
·
求解100~200之间的素数目录
前言
对于很多人对求解素数存在一定的困惑,在这里,我将用一些方法为大家讲解我的理解,希望可以帮助大家。下面是求解100~200之间素数的方法
一、素数是什么?
素数:素数也称质数,素数是指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数。(PS:7=1*7,7为素数)
二、求解素数的方法
1.常规方法
代码如下(示例):
#include<stdio.h>
//求解100~200之间的素数
int main()
{
int i = 0;
int j = 0;
int sum = 0; //sum 计数,统计100~200之间的素数个数
for (i = 100; i <= 200; i++) //规定范围
{
for (j = 2; j < i; j++) //素数的定义为只有两个因子:1和它本身
{
if (i % j == 0) //如果i%j==0 说明j也是i的因子,不满足质数的条件
{
break; //已经不满足的,跳出循环
}
}
if (j == i) //如果是质数,内循环中未进行break操作,j++到循环结束为i
{
printf("%d ", i); //输出i
sum++; //总数加一
}
}
printf("\nsum=%d\n", sum);
return 0;
}
2.优化代码
优化代码1如下(示例):
int main()
{
int i = 0;
int j = 0;
int sum = 0; //sum 计数,统计100~200之间的素数个数
for (i = 101; i < 200; i+=2) //100,200为偶数不考虑,100~200中的偶数都不考虑每次加2,跳过2
{
for (j = 2; j < i; j++) //素数的定义为只有两个因子:1和它本身
{
if (i % j == 0) //如果i%j==0 说明j也是i的因子,不满足质数的条件
{
break; //已经不满足的,跳出循环
}
}
if (j == i) //如果是质数,内循环中未进行break操作,j++到循环结束为i
{
printf("%d ", i); //输出i
sum++; //总数加一
}
}
printf("\nsum=%d\n", sum);
return 0;
}
通过对素数定义的理解,明白偶数(不包括0,2)一定不是素数,在循环过程中,不在考虑偶数,可以大大的提高代码的运算速度。
for (i = 101; i < 200; i+=2) //100,200为偶数不考虑,100~200中的偶数都不考虑每次加2,跳过2 { for (j = 2; j <= i/2; j++) //素数的定义为只有两个因子:1和它本身,i/2为上届 { if (i % j == 0) //如果i%j==0 说明j也是i的因子,不满足质数的条件 { break; //已经不满足的,跳出循环 } } if (j == i) //如果是质数,内循环中未进行break操作,j++到循环结束为i { printf("%d ", i); //输出i sum++; //总数加一 } }
for (i = 101; i < 200; i+=2) //100,200为偶数不考虑,100~200中的偶数都不考虑每次加2,跳过2 { for (j = 2; j <= sqrt(i); j++) //素数的定义为只有两个因子:1和它本身, { if (i % j == 0) //如果i%j==0 说明j也是i的因子,不满足质数的条件 { break; //已经不满足的,跳出循环 } } if (j == i) //如果是质数,内循环中未进行break操作,j++到循环结束为i { printf("%d ", i); //输出i sum++; //总数加一 } }
3.另辟蹊径
用函数的方法,或者采用一种特殊的方法,见如下():
#include<stdio.h>
int main()
{
int i = 0;
int sum = 0; //sum 计数,统计100~200之间的素数个数
for (i = 101; i < 200; i+=2) //100,200为偶数不考虑,100~200中的偶数都不考虑每次加2,跳过2
{
if (i % 2 != 0 && i % 3 != 0 && i % 5 != 0 && i % 7 != 0&&i%11!=0&&i%13!=0) //因为2,3,5,7,11,13为质数
{
printf("%d ", i);
sum++;
}
}
printf("\nsum=%d\n", sum);
return 0;
}
在100~200的范围中,如果可以整除质数,说明质数为其因子,不考虑其他数的原因是其他数拥有多个因子,质数只有两个因子,若整除质数都不等于0,说明包含的因子数只有1和它本身,则它一定是质数。
4.函数方法解决
#include<stdio.h>
#include<math.h>
int su(int a) //需要返回一个判断数
{
int i = 0;
for (i = 2; i <= sqrt(a); i++)
{
if (a % i == 0)
{
return 1; //不是质数返回1
break; //直接结束循环,函数结束
}
}
}
int main()
{
int i = 0;
int sum = 0;
for (i = 101; i < 200; i+=2)
{
if (su(i) != 1)
{
printf("%d ", i);
sum++;
}
}
printf("\nsum=%d\n",sum);
return 0;
}
总结
在这个题目中,我们需要了解质数的定义,明白判断条件,结束条件是什么。求赞,求关注呀!
更多推荐
已为社区贡献1条内容
所有评论(0)