题目描述
令 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
思路分析:
这个题, 判断素数大家都会, 重点是在于这个算法是否会超时, 以及输出格式的问题:
素数判断:
除了 1 和它本身, 没有其他的因子, 称为素数, 可以看成 循环变量从 2 到 n-1, 但是, 如果数非常大的话, 这就很头疼了,
咱们来简化一下判断素数的方法, 比如 n=9 时, 因为 9 开根等于 3, 所以, 判断到 3 就可以确定 9 不是素数, 因此, 循环变量 i 可以从 2 到根号下 n, 也就是 [2-sqrt(n)]
当一个数被确认是素数时, 就要输出了,
输出格式:
题目要求, 10 个一换行
那么咱就直接判断 count(从 2 开始累加的素数的个数), 分为 3 种情况:
1. 素数的位置小于题目要求的输出范围, 即 count<n, 这时候, 不输出, 继续循环;
2. 素数的位置在题目要求的输出范围, 首先行内输出素数, 这时, 素数后面的输出, 又分为 3 种情况:
1输出的素数不是一行的第 10 个, 即 (count-m+1)%10!=0,
例如题目给的测试用例, m=5, 当 count=5 时,(count-m+1)%10=1, 当 count=13 时,(count-m+1)%10=9,
这个时候需要输出一个空格 " ";
2输出的素数恰巧是一行的第 10 个, 即 (count-m+1)%10=0,
例如, 当 count=14 时,(count-m+1)%10 = 0 , 这个时候需要输出一个空行;
3数出的素数是要求输出的最后一个, 即 count=n, 这个时候, 直接结束程序即可;
3. 素数的位置大于题目要求的输出范围, 其实, 程序永远都走不到这一步, 当输出的素数是要求输出的最后一个时, 在第二种情况的第三点已经结束程序啦
Java 代码如下:
- import java.util.Scanner;
- public class Main {
- public static void main(String[] args) {
- Scanner sca = new Scanner(System.in);
- int m = sca.nextInt();
- int n = sca.nextInt();
- int count = 1;
- if(m == 1) {
- System.out.print(2);
- if(n == 1)
- return;
- else
- System.out.print(" ");
- }
- int i = 3;
- while(true){
- if(f(i)) { // 素数判断
- count++; // 素数数目 + 1
- if(count>= m) { // 素数的位置在题目要求的输出范围
- System.out.print(i);// 行内输出素数
- if(count==n){// 数出的素数是要求输出的最后一个, 结束程序
- return;
- }
- if((count-m+1) % 10 != 0) {//1(count-m+1)%10!=0, 输出空格 " "
- System.out.print(" ");
- }else { //1(count-m+1)%10==0, 输出空行
- System.out.println();
- }
- }
- }
- i+=2;
- }
- }
- // 判断素数
- static boolean f(int x){
- for(int j = 2; j < Math.sqrt(x) + 1; j++) {
- if(x % j == 0) {
- return false;
- }
- }
- return true;
- }
- }
来源: http://www.bubuko.com/infodetail-2930821.html