JAVA程式分享(課本習題-設計一個三角形類別)

Prime
跑很久的版本

1. import java.util.*;
   
2. public class Prime1 {
   
3.     public static void main(String[] args) {
   
4.                
   
5.                 int number=999999;
   
6.                 Boolean Prime=true;
   
7.                
   
8.                 for(int i=2;i<number;i++){
   
9.                         for(int j=2;j<i;j++){
   
10.                                        
    
11.                                         if ( i % j == 0){
    
12.                                                         Prime=false;                                                        
    
13.                                                 }
    
14.                         }
    
15.                         if (Prime) {
    
16.                                 System.out.print(i + " ");
    
17.                 }
    
18.                         Prime=true;
    
19.                 }
    
20.                
    
21.                 //System.out.println(number);
    
22.     }
    
23. }

複製代碼

第二種
因為質數在取餘數時for(int j=2;j<i/2;j++){，讓j中間的條件是做i/2
因為假設14是是要被程式檢驗是否為質數，14/2是7。
14/7=2餘0 對吧！
14/8=這邊的動作怎麼除都不會有整除和餘0的結果出現
14/9=這邊的動作怎麼除都不會有整除和餘0的結果出現
除非到了自己除自己，但找值數自己除自己，這個程式就會不正常運作.....且自己除自己一定會整除，且於數是0
要檢驗的數值只要檢驗要檢驗的數值除2就好，就樣就省下很多迴圈。
我把99999，1~99999質數以Prime1我的電腦要跑25秒左右，Prime2我的電腦要跑15秒。

1. import java.util.*;
   
2. public class Prime2 {
   
3.     public static void main(String[] args) {
   
4.                
   
5.                 int number=99999;
   
6.                 Boolean Prime=true;
   
7.                
   
8.                 for(int i=2;i<number;i++){
   
9.                         for(int j=2;j<i/2;j++){
   
10.                                        
    
11.                                         if ( i % j == 0){
    
12.                                                         Prime=false;                                                        
    
13.                                                 }
    
14.                         }
    
15.                         if (Prime) {
    
16.                                 System.out.print(i + " ");
    
17.                 }
    
18.                         Prime=true;
    
19.                 }
    
20.                
    
21.                 //System.out.println(number);
    
22.     }
    
23. }

複製代碼

第三種寫法就是把/2的地方做開根號，基本上開根號後找質數也可以，答案也正確....迴圈數又少了更多....大概你用999999(6個9)，一下就跑完了。
第三種作數學開根號，你打99999大概五秒做完....打六個999999，也很快做完。
其實這個演算法是跟數學有關，能以最少迴圈次數做完一件事情，且也要達到一樣的效果。
你有學到排序嗎？氣泡排序法最簡單的，氣泡排序在我腦海裡，直接可以寫出來，最基本的排序法，效率也很差。

1. import java.util.*;
   
2. public class Prime3 {
   
3.     public static void main(String[] args) {
   
4.                
   
5.                 int number=99999;
   
6.                 Boolean Prime=true;
   
7.                
   
8.                                 
   
9.                 for(int i=2;i<number;i++){
   
10.                         for(int j=2;j<Math.sqrt(i);j++){
    
11.                                        
    
12.                                         if ( i % j == 0){
    
13.                                                         Prime=false;                                                        
    
14.                                                 }
    
15.                         }
    
16.                         if (Prime) {
    
17.                                 System.out.print(i + " ");
    
18.                 }
    
19.                         Prime=true;
    
20.                 }
    
21.                
    
22.                 //System.out.println(number);
    
23.     }
    
24. }

複製代碼

所以我說完了1+2+3..+...1000，你用迴圈做一定很慢。(如果剛學for都會用迴圈)
但是為了效率...我絕對不會這樣寫，因為1+2.+3+...+10000有個叫梯型公式去算，不管數字多大，程式都一秒算完，這樣你懂了嗎！
你可以試試看我說的梯型公式， (1+1000)x1000/2=500500
和用for迴圈跑1+2+3...+1000最後算了很久跑出500500那差很多，如果1+2+3+...+1000如果用for迴圈跑你的電腦跑很快沒感覺到很慢的話，把1+2+3+...+N，把那個N改到JAVA的int最大值為2147483647。(其實也不用到這麼大改個999999六個9或是8個9或是9個9就很多了)
就這樣～

我最近在研究這組程式

算出2147000000質數有多少個只需要花10幾秒.....

不過幾乎看不懂.....

您認為這組程式寫得好嗎??

1. 
   
2. 
   
3. public class PrimeFinder {
   
4. 
   
5.     private static class BitSet {
   
6. 
   
7.         private int bits[];
   
8. 
   
9.         public BitSet(int n) {
   
10.             this.bits = new int[(n + 31) / 32];
    
11.         }
    
12. 
    
13.         public final boolean get(int index) {
    
14.             return (bits[index >> 5] & (1 << (index & 0x1F))) != 0;
    
15.         }
    
16. 
    
17.         public final void set(int index) {
    
18.             bits[index >> 5] |= (1 << (index & 0x1F));
    
19.         }
    
20. 
    
21.         public final int bitsCount() {
    
22.             int count = 0;
    
23.             for (int x : bits) {
    
24.                 for (; x != 0; x ^= (x & -x)) {
    
25.                     ++count;
    
26.                 }
    
27.             }
    
28.             return count;
    
29.         }
    
30.     }
    
31. 
    
32.     public int[] getPrimes(int range) {
    
33.         BitSet bitset = new BitSet(range + 1);
    
34.         int bound = (int) Math.sqrt(range);
    
35.         for (int i = 2; i <= bound; ++i) {
    
36.             if (bitset.get(i)) {
    
37.                 continue;
    
38.             }
    
39.             for (int j = i * i; j <= range; j += i) {
    
40.                 bitset.set(j);
    
41.             }
    
42.         }
    
43.         int count = range - 1 - bitset.bitsCount();
    
44.         int res[] = new int[count];
    
45.         for (int i = range; i > 1; --i) {
    
46.             if (!bitset.get(i)) {
    
47.                 res[ --count] = i;
    
48.             }
    
49.         }
    
50.         return res;
    
51.     }
    
52. 
    
53.     public int getPrimesCount(int range) {
    
54.         int primes[] = getPrimes((int) Math.sqrt(range));
    
55.         int start = 2, step = 262144, count = 0;
    
56.         while (start <= range) {
    
57.             int end = Math.min(range + 1, start + step);
    
58.             count += sift(primes, start, end);
    
59.             start = end;
    
60.         }
    
61.         return count;
    
62.     }
    
63. 
    
64.     private int sift(int primes[], int start, int end) {
    
65.         BitSet bitset = new BitSet(end - start);
    
66.         int e = end - start;
    
67.         for (int p : primes) {
    
68.             int s = (Math.max(p * p, start) + p - 1) / p * p - start;
    
69.             for (int j = s; j < e; j += p) {
    
70.                 bitset.set(j);
    
71.             }
    
72.         }
    
73.         return end - start - bitset.bitsCount();
    
74.     }
    
75. 
    
76.     public static void main(String argv[]) {
    
77.         int n = 2147000000;
    
78.         PrimeFinder engine = new PrimeFinder();
    
79.         long start = System.currentTimeMillis();
    
80.         System.out.println(engine.getPrimesCount(n));
    
81.         System.out.println(System.currentTimeMillis() - start);
    
82.     }
    
83. }
    
84. 
    

複製代碼

看不懂~知道他最後main有做一個...時間計時，我之前上面的也想寫，想想算了。

我上面的寫法令一種是當找到第一個數可以整除這個被檢驗的值數，這次的迴圈跳過，換下一個新的要被檢驗質數的數值。