数素数 (20)
时间限制 1000 ms 内存限制 32768 KB 代码长度限制 100 KB 判断程序 Standard (来自 小小)
题目描述
令Pi表示第i个素数。现任给两个正整数M <= N <= 10000，请输出PM到PN的所有素数。
输入描述:
输入在一行中给出M和N，其间以空格分隔。
输出描述:
输出从PM到PN的所有素数，每10个数字占1行，其间以空格分隔，但行末不得有多余空格。
输入例子:
5 27
输出例子:
11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103
解题思路：
- 注意是输出第5个素数与第27个素数之间的所有素数，而不是5到27内的素数！
- 素数一定出现在奇数内，如果某一个奇数不是素数那么它一定被奇数整除，所有就可以只检测奇数。
- 一个数若可以进行因数分解，那么分解时得到的两个数一定是一个小于等于sqrt(n)，一个大于等于sqrt(n)，据此，上述代码中并不需要遍历到n-1，遍历到sqrt(n)即可，因为若sqrt(n)左侧找不到约数，那么右侧也一定找不到约数。所以只搜索2~sqrt（n）即可；
代码实现：
/*
* 牛客网 PTA乙级真题 1003 数素数
*/
#include <stdio.h>
#include <math.h>int main()
{int N = 0, M = 0;int flag = 0;int cnt = 1;int out_cnt = 0;scanf("%d%d", &M, &N);if(M == 1){printf("%d", 2);out_cnt++;}for(int i = 3; ; i+=2){flag = 0;for(int j = 3; j <= pow(i, 0.5); j+=2)//检测素数，素数只能在奇数中出现，而且奇数如果不是素数也只能整除奇数 {if(i % j == 0){flag = 1;break;}}if(flag == 0)//素数 {if(++cnt >= M && cnt <= N){if((++out_cnt - 1) % 10 == 0)//每一行第一个打印的数字 {printf("%d", i);}else{printf(" %d", i);if(out_cnt % 10 == 0)//满10个回车 printf("\n");}}else if(cnt > N)//超出范围，结束循环 {break;} }}return 0;
}