C语言每日一题【入门】——打印素数

一、题目要求：

? ? 在数字100~200中，打印符合素数的要求的数

二、题目分析：

素数是什么？

? ? 素数的能被1和它本身整除的数；（1不是素数）

由此我们可以建立思路：

? ? 1.这里要用到两层嵌套循环（外层：循环这100个数字，内层：判断这100个数字是否是素数，符合数字要求打印出来）

? ? 2.假定一个数字 i ，若想判断 i 不是素数，则需保证2~(i-1),的除数，不能被 i 整除，也就是没有余数。

? ? 3.对于一个数，假定它是素数，创建一个变量flag，并初始化为1，若不符合要求将flag赋值为1；（这里的变量count是用来统计素数个数的）

? ? 4.打印结果是：

三、算法优化

初度优化：

我们在数学上应该知道这个东西：（sqrt() 是开平方函数）

? ? a = b*c,其中b和c的关系是怎么样的？其中必有一个因子b/c <= sqrt(a)，另一个因子c/b >= sqrt(a);

? ? 若a为素数，则b/c只能为1，c/b只能为a;? 这样我们只需要保证，2~sqrt（a）没有可被a整除的除数就可以判断a是素数，这样就可以省去一半的循环。

再次优化：

我们应该知道偶数不可能是素数，那循环可不可以直接从奇数101开始？，每次调整 i 都 +2 .

代码展示：

int main()
{
?? ?int i = 1;
?? ?int count = 0;
?? ?for (i = 101; i <= 200; ++i)
?? ?{
?? ??? ?int j = 0;
?? ??? ?int flag = 1;
?? ??? ?for (j = 2; j <= (int)sqrt(i); j++)
?? ??? ?{
?? ??? ??? ?if (!(i % j))
?? ??? ??? ?{
?? ??? ??? ??? ?flag = 0;
?? ??? ??? ??? ?break;
?? ??? ??? ?}
?? ??? ??? ??? ?
?? ??? ?}
?? ??? ?if (flag)
?? ??? ?{
?? ??? ??? ?printf("%d ", i);
?? ??? ??? ?count++;
?? ??? ?}
?? ?}
?? ?printf("\ncount == %d",count);
?? ?return 0;
}