素數(shù)在計算機中經(jīng)常被運用于計算機安全（密碼相關(guān)的計算），所以研究一下素數(shù)的判斷算法是相當(dāng)有必要的。所以現(xiàn)在就來看一下兩種比較常見的算法，試除法和Eratosthenes算法吧！

1、試除法

用需要驗證的數(shù) N 逐個除以從 2 開始至 N-1 中的所有數(shù)，若能被一個數(shù)整除，表示它有一個因數(shù)，說明數(shù) N 不是素數(shù)；若一直到 N-1 都不能被整除，則說明 N 是素數(shù)。（當(dāng)然我們對于因數(shù)的判斷不必計算到 N-1,只需要到 就可以了）

    public class Prime {

    public static boolean IsPrime(int num){
        for(int i=2;i*i<=num;++i){
            if(num % i==0){
                return false;
            }
        }
        return true;
    }

    public static void Usual(int size){
        int index = 0;
        for(int j=2;j<=size;++j){
            if(IsPrime(j)){
                index++;
                System.out.print(j + " ");
                if(index%10==0) System.out.print('\n');
            }
        }
    }

    public static void main(String[] args) {
        Usual(10000);
    }
    }

2、Eratosthenes算法

Eratosthenes算法的實現(xiàn)，其實就像是一個篩子，每次過濾掉合數(shù)，最后剩下的就是素數(shù)了，例如：如果要找出2~10000之間所有素數(shù)的算法，可以先過濾調(diào)用 2 的倍數(shù)，再過濾掉 3 的倍數(shù)，依次再5,7,11,13...97 就是
以內(nèi)的所有素數(shù)。剩下的就都是素數(shù)了。

    public class Prime {

    public static void Eratosthenes(int size){
        boolean[] nums = new boolean[size];
        // false 代表是素數(shù),默認是素數(shù)，關(guān)鍵的實現(xiàn)方式如下
        for(int i=2;i*i<size;++i){
            if(!nums[i]){
                //利用j+=i來判斷倍數(shù)，這里從j從i*i開始
                for(int j=i*i;j<size;j+=i){
                    nums[j]=true;
                }
            }
        }
        int index = 0;
        for(int i=2;i<size;++i){
            if(!nums[i]){
                index++;
                System.out.print(i + " ");
                if(index%10==0) System.out.print('\n');
            }
        }

    public static void main(String[] args) {
        Usual(10000);
    }
    }

兩種方法測試1000000個數(shù)據(jù)中找素數(shù)，對比如下

    public class Prime {
    
        public static boolean IsPrime(int num){
            for(int i=2;i*i<=num;++i){
                if(num % i==0){
                    return false;
                }
            }
            return true;
        }
    
        public static void Usual(int size){
            int length=0;
            for(int j=2;j<=size;++j){
                if(IsPrime(j)){length++;}
            }
            System.out.println(length);
        }
    
    
        public static void Eratosthenes(int size){
            int length=0;
            boolean[] nums = new boolean[size];
            // false 代表是素數(shù),默認是素數(shù)
            for(int i=2;i*2<size;++i){
                if(!nums[i]){
                    for(int j=i*2;j<size;j+=i){
                        nums[j]=true;
                    }
                }
            }
            for(int i=2;i<size;++i)if(!nums[i])length++;
            System.out.println(length);
        }
    
    
        public static void main(String[] args) {
            long last = System.currentTimeMillis();
            Usual(1000000);
            long now = System.currentTimeMillis();
            System.out.println("TotalTime:"+(now-last));
            last = now;
            Eratosthenes(1000000);
            now = System.currentTimeMillis();
            System.out.println("TotalTime:"+(now-last));
        }
    }

結(jié)果：

78498
TotalTime:798
78498
TotalTime:127

顯然，Eratosthenes算法效率高得多了。