第一天正式學習Java，寫下這篇關于質數求解的文章，希望能更改進的更好。
首先說，以前在C上求解過質數的問題，當時沒怎么在意。一直用的方法是從2開始遞增到n-1，如果在這個過程中有一個數能被n整除，那么這個數就不是質數。這樣做當然是沒問題的最簡單的一種方法。
之后看了一些文章的介紹，隨著數學知識的增長，今天在學習Java語言上實現了這個想法，把這一過程記錄如下：
先從最原始的遞增法說起：
1、除了2之外，全部的質數是奇數，所以，循環數可以減少一般。
2、遞增的界限不應是n-1，可以加以優化。對于整數N，存在最大的n，使得n的平方<=N，在自然數范圍內，N必定可以分解為兩個數的乘積，假設分解的結果是n1*n2=N，且n1<n2；那么必定有n1<n<n2。這樣得出結論，在求質數的過程中，遞增的最大的界限是N的二次方根。
3、實現代碼：（java）
// 判斷一個是是否是質數Scanner input=new Scanner(System.in);System.out.
//if..else:當輸入的數小于2時，顯示錯誤；當輸入的是2時，顯示是質數，當輸入的是大于2的數時，開始循環判斷if(number<2){ System.out.println("輸入非法，請輸入大于2的整數。程序終止");}else if(number==2){ System.out.println("2 是質數");}else{ //如果能被2整除修改flag,否則從3開始for循環判斷是否修改flag if(number%2==0){ flag=false; }else{ for(int i=3;i<=Math.sqrt(number);i+=2){ if(number%i==0){ flag=false; break; } } } //根據flag是否被修改，判斷時候是質數 if(flag){ System.out.println(number+"是質數"); }else{ System.out.println(number+"不是質數"); }}
4、對于打印n內所有的質數的問題，用上面的方法一個一個的判斷是非常浪費資源的。使用曬法打印效率會高很多。
5、曬法的基本思想是除去N內所有質數倍數的數，剩下的就是質數，比如打印10以內的質數：
從a=2開始，先除去2倍數的數，即4、6、8；
a++，3，沒被除去必是質數，再除去3倍數的數，6，9；
a++，4，已經被除去，循環繼續；
a++，5，沒被除去必是質數，除去5的倍數10；
到這步，由于至少需要除去質數的2倍的數，即，循環的最大數是n/2。對于大于n/2再處理，如果它沒有被前面的操作除去，那么它必定是質數。
代碼實現（Java）：
//篩選法,實現100以內所有素數的打印 byte[] bl=new byte[100]; //k用來存儲每個待除去的數組下標 int k; //將所有的值設為1 for(int j=0;j<100;j++){ bl[j]=1; } //曬法實現去除所有非質數 for(int i=1;i<=50;i+=1){ //如果這個數組值不為1,則繼續 if(bl[i]==0){ continue; } for(int j=i;j<100/(i+1);j++){ k=(i+1)*(j+1)-1; bl[k]=0; } } System.out.print('2'+" "); for(int i=2;i<100;i+=2){ if(bl[i]==1) System.out.print((i+1)+" "); } System.out.println(); //結果應該是 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 }
新聞熱點
疑難解答
