打印素数
题目描述
使⽤C语⾔写⼀个程序打印100~200之间的素数,数字中间使⽤空格分割。
解题思路
素数是指只能被1和它本⾝整除的正整数。我们可以遍历100~200,并找出哪些数字是素数,这⾥给 出⼏个判断 数字 x 是否为素数的⽅法:
- 试除法:
- a. 从 2 到 x-1,逐个尝试是否能整除 x,如果能,x 就不是素数,否则 x 是素数。
- b. 当 x 为偶数时,x ⼀定不是素数,因此在遍历时我们可以跳过每个偶数。
- 试除法时间优化:
- a. 当 2 到 x-1 中存在某个数 t 可以整除 x 时,令 d=x/t,则 d 也可以整除 x,并且结果为 t。因此,当 2~√x 中不存在可以整除 x 的数时,√x+1~x 也不存在可以整除 x 的数。
- b. 利⽤反证法证明:
- i. 假设 2 到 x-1 中不存在可以整除 x 的数,√x+1~x 中存在⼀个数 d 可以整除 x;
- ii. 存在另⼀个数 t=x/d 也可以整除 x;
- iii. t*d=x,因为 d>√x,所以 t<√x,即 2 到 x-1 中存在某个数 t 可以整除 x;
- iv. 与假设⽭盾,反证成⽴。
解法代码
//⽅法1
#include <stdio.h>
int main()
{
int i = 0;
for (i = 100; i <= 200; i++)
{
int j = 0;
//判断i是否为素数
int flag = 1;//定义变量记录当前数是否为素数,假设是素数,变量值为1
//遍历2~当前数-1
for (j = 2; j < i; j++)
{
//存在⼀个数可以整除当前数
if (i % j == 0)
{
flag = 0;//不是素数
break;
}
}
if (flag == 1)//是素数就打印
printf("%d ", i);
}
return 0;
}
//优化1
#include <stdio.h>
int main()
{
int i = 0;
//因为偶数不是素数,直接跳过
for (i = 101; i <= 200; i += 2)
{
int j = 0;
//判断i是否为素数
int flag = 1;//定义变量记录当前数是否为素数,假设是素数,变量值为1
//遍历2~当前数-1
for (j = 2; j < i; j++)
{
//存在⼀个数可以整除当前数
if (i % j == 0)
{
flag = 0;//不是素数
break;
}
}
if (flag == 1)//是素数就打印
printf("%d ", i);
}
return 0;
}
//优化2
#include <stdio.h>
#include <math.h>
int main()
{
int i = 0;
//因为偶数不是素数,直接跳过
for (i = 101; i <= 200; i += 2)
{
int j = 0;
//判断i是否为素数
int flag = 1;//定义变量记录当前数是否为素数,假设是素数,变量值为1
//遍历2~当前数的根号
for (j = 2; j <= sqrt(i); j++)
{
//存在⼀个数可以整除当前数
if (i % j == 0)
{
flag = 0;//不是素数
break;
}
}
if (flag == 1)//是素数就打印
printf("%d ", i);
}
return 0;
}
运行结果
101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199