JWorld@TW the best professional Java site in Taiwan
      註冊 | 登入 | 全文檢索 | 排行榜  

» JWorld@TW » Java 程式分享區  

按列印兼容模式列印這個話題 列印話題    把這個話題寄給朋友 寄給朋友    訂閱主題
reply to topicthreaded modego to previous topicgo to next topic
本主題所含的標籤
無標籤
作者 [教學]找質數程式
shumi

看書的兔寶~



發文: 12
積分: 3
於 2004-04-08 08:51 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
http://www.javaworld.com.tw/blog/archives/ciyawasay/000100.html

質數的定義:除了1之外的自然數只能被1或自己整除的數

方法是從2開始找到質數後存入一個陣列
以後的數都拿之前找到的質數來判斷是否整除
除數的範圍就是質數的第一個到比被除數開根號小的質數

ex:要判斷12是不是質數 先開根號取整數+1得4
用找到的質數去除 就是除以2和3結果整除 所以不是質數
但其實只除以2就判斷出他不是質數了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class DetectPrime{
   public static void main(String[] args){
      long before = System.currentTimeMillis();
      int number = 100;
      if(args.length == 1){
         try{
            number = Integer.parseInt(args[0]);
         }catch(Exception e){
            System.err.println(e);
         }
      }
      int[] primes = new int[number];
      primes[0] = 2;
      int count = 0;
      
      for(int i = 2; i < number; i++){
         
         boolean prime = true;
         int max = (int)Math.sqrt(i) + 1;
         
         for(int j = 0; primes[j] < max; j++){
            if((i % primes[j]) == 0){
               prime = false;
               break;
            }
         }
         
         if((i == 0)||(i == 1)) continue;
         if(prime){
            primes[count] = i;
            System.out.println(i);
            count++;
         }
      }
      long after = System.currentTimeMillis();
      System.out.print("1~" + number + "有" + count +"個質數");
      System.out.print("共花了" + (after-before) + "milliseconds");
   }
}


reply to postreply to post
作者 Re:[教學]找質數程式 [Re:shumi]
caterpillar

良葛格

版主

發文: 2593
積分: 70
於 2004-04-08 16:55 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
順便參考一下:Eratosthenes篩選求質數
http://openhome.cc/Gossip/AlgorithmGossip/EratosthenesPrime.htm

簡單的說,您是用找到的質數去除還沒判斷的數,而Eratosthenes篩選更進一步直接將這些數篩去,這樣檢查的次數可以更少。。。。

有興趣的請將我的C語言版本改為Java版本,可以加分,另下面的補充實現與說明原理者也都可以加分!


caterpillar edited on 2013-04-06 16:58
reply to postreply to post
良葛格學習筆記
作者 Re:[教學]找質數程式 [Re:shumi]
sungo

瘋狂口罩大盜



發文: 822
積分: 17
於 2004-04-08 17:50 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
將良葛格站上的『Eratosthenes篩選求質數』C語言版本改成Java版。

第一次PO的程式碼,Integer.parseInt(N)寫在迴圈裡
,會造成效率不好的問題(because N is not final, so
the compiler does not know N will be unchange)
因此稍作修改,感謝T55555的提點。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.io.*;
public class Test {
    public static void main(String args[]) throws IOException {
        int i = 0;
        int j = 0;
        int N = 0;
        BufferedReader buf =
            new BufferedReader(new InputStreamReader(System.in));
        System.out.print("請輸入查詢質數的範圍:");
        try {
            N = Integer.parseInt(buf.readLine());
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(1);
        }
        int[] prime = new int[N + 1];
        for (i = 2; i <= N; i++)
            prime[i] = 1;
        for (i = 2; Math.pow(i, 2) <= N; i++) {
            if (prime[i] == 1) {
                for (j = 2 * i; j <= N; j++) {
                    if (j % i == 0)
                        prime[j] = 0;
                }
            }
        }
        for (i = 2; i < N; i++) {
            if (prime[i] == 1) {
                System.out.print(i + "  ");
                if (i % 16 == 0)
                    System.out.print("\n");
            }
        }
    }
}
Output:
1
2
請輸入查詢質數的範圍:9
2  3  5  7  


sungo edited on 2004-04-09 06:46
reply to postreply to post
作者 Re:[教學]找質數程式 [Re:shumi]
TIJ_Rob





發文: 23
積分: 0
於 2004-08-13 00:12 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
這個範例(from bruceEckel.com的解答)應該比較容易懂,前面幾位大大的程式我不是很懂,因為我已經很久沒碰數學了!!@@
這個程式主要是要用兩個for迴圈及%來偵測質數(不然還能用什麼..)
注意 第二個迴圈沒有{}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class FindPrimes {
    public static void main(String[] args) {
    int max = 100;
    // Get the max value from the command line,
    // if the argument has been provided:
    if (args.length != 0)
      max = Integer.parseInt(args[0]);
    for (int i = 1; i < max; i++) {
      boolean prime = true;
      for (int j = 2; j < i; j++)
        if (i % j == 0) 
           prime = false;
      if (prime)
        System.out.print(i+" ");
    }
  }
}

程式結果如下:
1
1 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 


TIJ_Rob edited on 2004-08-13 16:05
reply to postreply to post
作者 Re:[教學]找質數程式 [Re:shumi]
rainystar

愛吃魚



發文: 147
積分: 1
於 2004-08-13 09:48 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
這段..
1
2
3
      for (int j = 2; j < i; j++)  
            if (i % j == 0)   
             prime = false;

改成
1
2
3
4
5
6
      for (int j = 2; j < i; j++){  
            if (i % j == 0){   
                  prime = false;
                  break;
            }
      }

可以擠出點效能


reply to postreply to post
作者 Re:[教學]找質數程式 [Re:rainystar]
TIJ_Rob





發文: 23
積分: 0
於 2004-08-13 15:57 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
1
2
3
4
5
6
      for (int j = 2; j < i; j++){  
            if (i % j == 0){   
                  prime = false;
                  break;
            }
      }

可以擠出點效能
我看了其他有關執行速度的文章裡面所提到的測試方法,基本上是不是就像以下這樣(加上程式中的兩行紅字)?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class E09_FindPrimes {
  public static void main(String[] args) {
    long a = System.currentTimeMillis();    
     int max = 100;
    // Get the max value from the command line,
    // if the argument has been provided:
    if (args.length != 0)
      max = Integer.parseInt(args[0]);
    for (int i = 1; i < max; i++) {
      boolean prime = true;
      for (int j = 2; j < i; j++)
        if (i % j == 0) {
          prime = false;
          break;        
        }
      if (prime)
        System.out.print(i+" ");
    }
    long b = System.currentTimeMillis();
    System.out.println("time spent:\t"+(b-a));  
  }
}


利用程式裡面前後的兩個時間點來計算整個執行所花費的時間,我猜是這樣,不知道這樣解釋是不是很正確??如果是這樣的話,那要如何確定這兩個long變數放的位置是對的?
(最前面跟最後面?這我也知道...Wink

BTW,基本上我依照上面一位作者所說的在裡面加入一行 break;
加這一行的差異要在偵測範圍很大時才會明顯的出現差距!ex.10000 不然在10之內找其實並沒有什麼差別!


TIJ_Rob edited on 2004-08-13 16:09
reply to postreply to post
作者 Re:[教學]找質數程式 [Re:shumi]
rainystar

愛吃魚



發文: 147
積分: 1
於 2004-08-13 16:50 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
package rainystar;
/**
 * User: rainystar
 * Date: 2004/8/13
 * Time: 下午 04:19:35.
 */
public class FindPrimes {
    public static void main(String args[]){
        int range=0;
        int index=-1;
        int[]  primes;
        try{
            if (args.length != 0) range=Integer.parseInt(args[0]);
            if(range<=2) throw new Exception();
        }catch(Exception ex){
            System.out.println("請輸入大於1的整數");
            System.exit(1);
        }
        primes=new int[range];
        for(int i=2;i<range;i++){
            if(isPrime(i,primes,index)) {
                index++;
                primes[index]=i;
                System.out.println(index+":"+i);
            }
        }
    }
 
    public static boolean isPrime(int value,int[] primes,int index){
        if(value==2) return true;
        for(int i=0;i<index;i++){
            if(primes[i]>Math.sqrt(value)) return true;
            if(value%primes[i]==0) return false;
        }
        return true;
    }
}


這個應該可以快很多吧Big Smile


rainystar edited on 2004-08-13 16:56
reply to postreply to post
作者 Re:[教學]找質數程式 [Re:shumi]
passerby





發文: 2
積分: 0
於 2004-12-01 08:19 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
不如直接篩去算了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Prime {
  public static void main(String args[]) {
    long before = System.currentTimeMillis();
    int count=0, number=100000;
    int primes[] = new int[number+1];
    for (int i=2; i <= number; i++) {
      if (primes[i] == 0) {
        //System.out.println(i);
        count++;
        for(int j=i; j <= number; j+=i) {
          primes[j] = 1;
        } // j
      } // if
    } // i
    long after = System.currentTimeMillis();
    System.out.print("1~" + number + "有" + count +"個質數");
    System.out.print("共花了" + (after-before) + "milliseconds");
  }
}


passerby edited on 2004-12-01 08:49
reply to postreply to post
作者 Re:[教學]找質數程式 [Re:shumi]
落日醉心





發文: 9
積分: 0
於 2006-11-19 00:49 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
感謝大大的分享與教學~
總算搞懂質數的驗算方式


reply to postreply to post
作者 Re:[教學]找質數程式 [Re:passerby]
cjack





發文: 291
積分: 1
於 2006-12-04 15:38 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
passerby大大的概念實在很精采
小弟稍微修飾一下,使得哪些數為質數也可以被秀出來
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class myPrime {
  public static void main(String args[]) {
    
    long before = System.currentTimeMillis();
    
    if(!(args.length>0))
        System.exit(1);
    
    int idx = Integer.parseInt(args[0]);
    boolean[] prime= new boolean[idx];
    
    for(int i=2;i<idx;i++){
      for(int j=(i+i);j<idx;j+=i){
        prime[j]=true;
      }
    }
    
    long after = System.currentTimeMillis();
    
    for(int i=2;i<idx;i++)
      if(!prime[i])System.out.print(i + " |");
    
    System.out.println("\nSpend Time:"+(after-before));
  }
}


reply to postreply to post
En Taro Adun!
作者 Re:[教學]找質數程式 [Re:cjack]
阿刃

生活就像 RPG



發文: 121
積分: 3
於 2007-04-27 22:00 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
cjack wrote:
passerby大大的概念實在很精采
小弟稍微修飾一下,使得哪些數為質數也可以被秀出來
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class myPrime {
  public static void main(String args[]) {
    
    long before = System.currentTimeMillis();
    
    if(!(args.length>0))
        System.exit(1);
    
    int idx = Integer.parseInt(args[0]);
    boolean[] prime= new boolean[idx];
    
    for(int i=2;i<idx;i++){
      for(int j=(i+i);j<idx;j+=i){
        prime[j]=true;
      }
    }
    
    long after = System.currentTimeMillis();
    
    for(int i=2;i<idx;i++)
      if(!prime[i])System.out.print(i + " |");
    
    System.out.println("\nSpend Time:"+(after-before));
  }
}



由於最近在寫平行化程式...剛好也寫到了找質數程式....才把這篇舊文又拿出來討論
((XD都已經寫完了才發現原來這邊已經有單機版的~只是做法不太一樣))

於是小弟把原本平行化的程式改成單機版...並拿掉數學最佳化後
和樓上這位大大的程式進行了點運算時間的比較...
((所謂的數學最佳化是...陣列的數字沒必要每個都拿來進行對質數的比對~只需要比到目標直開根號的數值就好了,舉例來說輸入的數字是100..只需要把2~10拿來算就可以))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
MyPrime==>樓上大大的程式
MyPrimeRefine==>小弟自行撰寫之平行化程式的單機版(未數學最佳化)
MyPrimeRefineUltra==>最佳化之版本
實驗環境:
OS: Windows XP SP2
JRE: 1.6.0_01
CPU: Pentium 4 3.00GHz((HT))
RAM: 1G
方法==>每隻程式各跑五次~計算其平均值~參數設定為10000000
 
結果:
MyPrime: (6672+6656+6609+6672+6610)/5 = 6643.8
MyPrimeRefine: (1031+1015+1062+1047+1110)/5 = 1053
MyPrimeUltra: (750+718+719+703+719)/5 = 721.8


我想速度上差異的主因是樓上大大的程式碼裡面很多次重複的比對
如: 2以經比對過了..卻又比對4..

並附上程式供大家參考...

如果有其他先進願意和小弟討論這隻程式的平行化...
也還請賜教

註:壓縮檔中之MyPrime.java為樓上大大所撰寫之程式碼

Prime.rar (2.37k)


reply to postreply to post
A never ending story with Java...

My blog => 【刃™】ThiS WORLD, MY WORLD
作者 Re:[教學]找質數程式 [Re:阿刃]
owenlin_twn





發文: 21
積分: 3
於 2007-04-29 14:57 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
阿刃 wrote:
如果有其他先進願意和小弟討論這隻程式的平行化...
也還請賜教
註:壓縮檔中之MyPrime.java為樓上大大所撰寫之程式碼

Hello, 我剛好之前研究過這個題目,想過了許多演算法來計算 2 ~ n 的質數個數。

那時發現,如果將 程式中的 prime 折起來作,也就是第一次先刪去 2 ~ 1000 的非質數,第二次再刪去 1000 ~ 2000。如此一來,雖然計算量幾乎是一樣的,但因為 prime 可以暫時放入 cache 中,可以大大的加快它的速度。另外,為了使 prime 的使用更有效率,我改用 bitset 來作。 ( 不知道為什麼,java 的 bitset 很慢,可能有作 input check 吧,所以我就自已寫了一個了小型的來用。)

我昨天改寫了之前用 c++ 寫的程式。試跑了一下,大約只要 130 ms 就可以算完 2~10000000 之間的質數個數了。

不知道您的平行化是怎麼作的?因為上面講的折疊法,也非常適合用在 parallel computing 上。不同的 task 之間,幾乎沒有關連性。如果 每個 cpu 有獨立的 cache 的話,相信 cache 加速的效果也不會打折。

我之前研究 計算質數個數的結果可以在 我的Wiki 中找到,也有之前各種演算法的 c++ 實作程式下載。

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


reply to postreply to post
作者 Re:[教學]找質數程式 [Re:owenlin_twn]
阿刃

生活就像 RPG



發文: 121
積分: 3
於 2007-04-29 16:05 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
owenlin_twn wrote:
那時發現,如果將 程式中的 prime 折起來作,也就是第一次先刪去 2 ~ 1000 的非質數,第二次再刪去 1000 ~ 2000。如此一來,雖然計算量幾乎是一樣的,但因為 prime 可以暫時放入 cache 中,可以大大的加快它的速度。另外,為了使 prime 的使用更有效率,我改用 bitset 來作。 ( 不知道為什麼,java 的 bitset 很慢,可能有作 input check 吧,所以我就自已寫了一個了小型的來用。)


以目前來說~小弟實做出的方法中~最快速的方法~應如同您所說的方式
舉例來說~若要找出10000000之所有質數
把原始要處理的資料除以n(所有可以使用的電腦數)
然後每台電腦負責處理原始資料集1/n的資料量
而每台電腦一樣是找出該資料集中小於10000000的質數
理論上最好的情形
每台電腦的處理時間會變成原本一台電腦的1/n
這種方式有比較好的負載平衡

以上心得分享^__^感謝您提出您的想法


reply to postreply to post
A never ending story with Java...

My blog => 【刃™】ThiS WORLD, MY WORLD
作者 Re:[教學]找質數程式 [Re:shumi]
psychokiller





發文: 581
積分: 1
於 2007-05-23 09:42 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
用C 寫的
已經忘了原來的author 是誰
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<string.h>
#include<stdio.h>
#include<memory.h>
#define MAXSIEVE 20000000 // All prime numbers up to this
#define MAXSIEVEHALF 10000000
#define MAXSQRT 2237 // sqrt(MAXSIEVE)/2
#define isprime(n) (a[(n)>>4]&(1<<(((n)>>1)&7))) // Works when n is odd
char a[MAXSIEVE/16+2];
int main(){
int i,j;
int input;
int counter=2;
memset(a,255,sizeof(a));
a[0]=0xFE;
for(i=1;i<MAXSQRT;i++)
if (a[i>>3]&(1<<(i&7)))
for(j=2*i*(i+1);j<MAXSIEVEHALF;j+=i+i+1)
a[j>>3]&=~(1<<(j&7));
 
return 0;
}


reply to postreply to post
» JWorld@TW »  Java 程式分享區

reply to topicthreaded modego to previous topicgo to next topic
  已讀文章
  新的文章
  被刪除的文章
Jump to the top of page

JWorld@TW 本站商標資訊

Powered by Powerful JuteForum® Version Jute 1.5.8