天天看點

java求素數和求一個數的一個正整數的質因數

1、題目:古典問題:有一對兔子,從出生後第3個月起每個月都生一對兔子,小兔子長到第四個月後每個月又生一對兔子,假如兔子都不死,問每個月的兔子總數為多少對?

  (1)程式分析:不難發現兔子的規律是:1,1,2,3,5,8,13,21....

    其實這個問題也就是求斐波那契數列的問題。

  (2)思路:應用遞歸來實作。1,2月的時候總數為一對,從第三個月開始就會産生一個新兔子,總數為2對,也就是born(n-1)+born(n-2)

  (3)代碼實作:

1 /**
 2  * 題目:古典問題:有一對兔子,從出生後第3個月起每個月都生一對兔子,小兔子長到第四個月後每個月又生一對兔子,假如兔子都不死,問每個月的兔子總數為多少?
 3  * @author lixiaochao
 4  * 兔子的規律為:1,1,2,3,5,8,13,21....
 5  */
 6 public class Rabbit {
 7     public static void main(String[] args) {
 8         int n = 5;   //月
 9         int m = 0;   //兔子總數
10         m = born(n);
11         System.out.println("一共有"+m);
12     }
13     public static int born(int n){
14         if(n == 1){
15             return 1;
16         }else if(n == 2){
17             return 1;
18         }else{
19             return born(n-1)+born(n-2);
20         }
21     }
22     
23 }      

  總結:當時看這個問題的時候,一看有點繞,而且很容易繞暈了,我們現在開始把他列舉一下,進而發現出規律,然後轉換一下求斐波那契數列的問題,這個問題就會很容易做了。

    有的時候我們可以轉換一下思路,問題有可能會變得很簡單的。

2、判斷101-200之間有多少個素數,并輸出所有的素數,

  (1)分析:首先我們要先了解判斷素數的方法是什麼,用一個數分别去除2到sqrt(這個數),如果能被整除,則表明此數不是素數,反之是素數。這種方法非常簡單效率也非常快。

  (2)思路:略。(因為比較簡單,是以省略掉了,如果大家對這個有疑問,可以留言告訴我)

  (3)代碼:

1 /**
 2      * 判斷101-200之間有多少個素數,并輸出所有素數。
 3      * 
 4      * 分析:判斷素數的方法:用一個數分别去除2到sqrt(這個數),如果能被整除,則表明此數不是素數,反之是素數
 5      */
 6 //    @Test
 7     public void test01(){
 8         int num = 0;
 9         
10         List<Integer> list = new ArrayList<Integer>();
11         for(int i = 101; i < 201; i++){
12             boolean flag = true;   //每次執行的時候把flag置為true
13             for(int j = 2; j < Math.sqrt(i)+1;j++){
14                 if(i % j == 0){
15                     flag = false;
16                     break;
17                 }
18             }
19             if(flag){
20                 num ++;
21                 list.add(i);
22                 System.out.println(i);
23             }
24         }
25         System.out.println("素數的個數為:"+num);
26         for(Integer n : list){
27             System.out.println(n);
28         }
29     }
30           

  總結:對于問題,我們要先想好解決問題的最好的方法,不要急于寫代碼,找到合理的算法才是解決問題最有效的途徑。

3、将一個正整數分解質因數。例如:輸入90,列印出90=2*3*3*5。 

  (1)分析:

    對n進行分解質因數,應先找到一個最小的質數i,然後按下述步驟完成: 

    * (1)如果這個質數恰等于n,則說明分解質因數的過程已經結束,列印出即可。

    * (2)如果n > i,但n能被i整除,則應列印出i的值,并用n除以i的商,作為新的正整數,重複執行第一步。

    * (3)如果n不能被i整除,則用i+1作為i的值,重複執行第一步。

  (2)思路:先找到一個最小的質數i,這個數n是否能夠整除這個最小的質數i,如果能整除,則n=n/i,如果不能整除,i=i+1,在再判斷這個是n是否能夠整除i+1,當這個質數恰好等于n的時候分解質因數結束。

  (3)代碼如下:

1 /**
 2      * 将一個正整數分解質因數。例如:輸入90,列印出90=2*3*3*5。 
 3      * 程式分析:對n進行分解質因數,應先找到一個最小的質數i,然後按下述步驟完成: 
 4      * (1)如果這個質數恰等于n,則說明分解質因數的過程已經結束,列印出即可。
 5      * (2)如果n > i,但n能被i整除,則應列印出i的值,并用n除以i的商,作為新的正整數,重複執行第一步。
 6      * (3)如果n不能被i整除,則用i+1作為i的值,重複執行第一步。
 7      * 
 8      */
 9     @Test
10     public void test(){
11         int n = 7;
12         int i = 2;
13         while(true){
14             if(n == i){
15                 System.out.println(i);
16                 break;
17             }
18             if(n%i == 0){
19                 System.out.println(i);
20                 n = n / i;
21             }else{
22                 i = i+1;
23             }
24         }
25     }      

  總結:多看,多想,多練!!!