1003：數(shù)素?cái)?shù) (20)

時(shí)間限制?1000 ms?內(nèi)存限制?32768 KB?代碼長度限制?100 KB?判斷程序?Standard?(來自?小小)

題目描述

令Pi表示第i個(gè)素?cái)?shù)?，F(xiàn)任給兩個(gè)正整數(shù)M <= N <= 10000，請(qǐng)輸出PM到PN的所有素?cái)?shù)。

輸入描述:

輸入在一行中給出M和N，其間以空格分隔。

輸出描述:

輸出從PM到PN的所有素?cái)?shù)，每10個(gè)數(shù)字占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


思路分析：

這個(gè)題，判斷素?cái)?shù)大家都會(huì)，重點(diǎn)是在于這個(gè)算法是否會(huì)超時(shí)，以及輸出格式的問題：

素?cái)?shù)判斷：
除了1和它本身，沒有其他的因子，稱為素?cái)?shù)， 可以看成 循環(huán)變量從2到n-1,但是，如果數(shù)非常大的話，這就很頭疼了，
咱們來簡化一下判斷素?cái)?shù)的方法，比如n=9時(shí)，因?yàn)?開根等于3，所以，判斷到3就可以確定9不是素?cái)?shù)，因此，循環(huán)變量i可以從2到根號(hào)下n，也就是【2-sqrt（n）】
當(dāng)一個(gè)數(shù)被確認(rèn)是素?cái)?shù)時(shí)，就要輸出了，

輸出格式：

題目要求，10個(gè)一換行
那么咱就直接判斷count（從2開始累加的素?cái)?shù)的個(gè)數(shù)），分為3種情況：

1.素?cái)?shù)的位置小于題目要求的輸出范圍，即count<n,這時(shí)候，不輸出，繼續(xù)循環(huán)；
2.素?cái)?shù)的位置在題目要求的輸出范圍，首先行內(nèi)輸出素?cái)?shù)，這時(shí)，素?cái)?shù)后面的輸出，又分為3種情況：
　?、佥敵龅乃?cái)?shù)不是一行的第10個(gè)，即(count-m+1)%10!=0,
　　　例如題目給的測(cè)試用例，m=5,當(dāng)count=5時(shí)，（count-m+1）%10=1，當(dāng)count=13時(shí)，（count-m+1）%10=9，
　　 這個(gè)時(shí)候需要輸出一個(gè)空格“ ”； 　?、谳敵龅乃?cái)?shù)恰巧是一行的第10個(gè)，即（count-m+1）%10=0,
　　　例如，當(dāng)count=14時(shí)，（count-m+1）%10 = 0 ,這個(gè)時(shí)候需要輸出一個(gè)空行；
　?、蹟?shù)出的素?cái)?shù)是要求輸出的最后一個(gè)，即count=n，這個(gè)時(shí)候，直接結(jié)束程序即可；

3.素?cái)?shù)的位置大于題目要求的輸出范圍，其實(shí)，程序永遠(yuǎn)都走不到這一步，當(dāng)輸出的素?cái)?shù)是要求輸出的最后一個(gè)時(shí)，在第二種情況的第三點(diǎn)已經(jīng)結(jié)束程序啦

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;elseSystem.out.print(" ");}int i = 3;while(true){if(f(i)) { //素?cái)?shù)判斷count++; //素?cái)?shù)數(shù)目+1if(count >= m) { //素?cái)?shù)的位置在題目要求的輸出范圍System.out.print(i);// 行內(nèi)輸出素?cái)?shù)if(count==n){//數(shù)出的素?cái)?shù)是要求輸出的最后一個(gè)，結(jié)束程序return;}if((count-m+1) % 10 != 0) {//①(count-m+1)%10!=0,輸出空格“ ”System.out.print(" ");}else { //①(count-m+1)%10==0,輸出空行 System.out.println();}}} i+=2;}}//判斷素?cái)?shù)static boolean f(int x){for(int j = 2; j < Math.sqrt(x) + 1; j++) {if(x % j == 0) {return false;} }return true;} }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/l199616j/p/10307179.html

與50位技術(shù)專家面對(duì)面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的牛客网 PAT 算法历年真题 1003： 数素数 (20)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。