package com.aekc.algorithm;

import java.util.Scanner;

/**
 * 求n以內(nèi)的所有素?cái)?shù)
 */
public class PrimeNumber {

    /**
     * 窮舉法螟碎，檢測(cè)所有可能的因子工秩。
     * 時(shí)間復(fù)雜度為：O(n^2)
     */
    public void primeNumber1(int n) {
        int number = 2;
        int count = 0;
        while(number <= n) {
            boolean isPrime = true;
            for(int divisor = 2; divisor <= number / 2; divisor++) {
                if(number % divisor == 0) {
                    isPrime = false;
                    break;
                }
            }
            if(isPrime) {
                count++;
            }
            number++;
        }
        System.out.println("\ncount: " + count);
    }

    /**
     * 檢測(cè)直到√n的因子
     * 時(shí)間復(fù)雜度為：O(n√n)
     */
    public void primeNumber2(int n) {
        int number = 2;
        int count = 0;
        while(number <= n) {
            boolean isPrime = true;
            int squareRoot = (int) Math.sqrt(number);
            for(int divisor = 2; divisor <= squareRoot; divisor++) {
                if(number % divisor == 0) {
                    isPrime = false;
                    break;
                }
            }
            if(isPrime) {
                count++;
            }
            number++;
        }
        System.out.println("\ncount: " + count);
    }

    /**
     * 檢測(cè)直到√n的素?cái)?shù)因子
     * 簡(jiǎn)易證明：如果i不是素?cái)?shù)炭晒，那就必須存在一個(gè)素?cái)?shù)p搭儒，滿足i=pq且p<=q惑淳。
     * k也是i的最小因子，這和p是i的最小因子是沖突的刃滓。因此狂票，如果i不是素?cái)?shù)，
     * 那么可以找出2到√i之間的被i整除的素?cái)?shù)蚊锹。
     * 時(shí)間復(fù)雜度為：O(n√n / logn)
     */
    public void primeNumber3(int n) {
        int number = 2;
        int count = 0;
        int squareRoot = 1;
        int[] primes = new int[n];
        while(number <= n) {
            boolean isPrime = true;
            if(squareRoot * squareRoot < number) {
                squareRoot++;
            }
            for(int k = 0; k < count && primes[k] <= squareRoot; k++) {
                if(number % primes[k] == 0) {
                    isPrime = false;
                    break;
                }
            }
            if(isPrime) {
                primes[count] = number;
                count++;
            }
            number++;
        }
        System.out.println("\ncount: " + count);
    }

    /**
     * 埃拉托色尼篩選算法
     * 利用當(dāng)前已經(jīng)找到的素?cái)?shù)瞳筏，從后面的數(shù)中篩去當(dāng)前素?cái)?shù)的倍數(shù)
     * 但是某些數(shù)被每個(gè)質(zhì)因子都篩了一遍導(dǎo)致速度減慢，空間開銷大
     * 時(shí)間復(fù)雜度為：O(n√n / logn) 接近于 O(n)
     */
    public void primeNumber4(int n) {
        boolean[] primes = new boolean[n + 1];
        for(int i = 0; i < primes.length; i++) {
            primes[i] = true;
        }
        for(int k = 2; k <= n / k; k++) {
            if(primes[k]) {
                for(int i = k; i <= n / k; i++) {
                    primes[k * i] = false;
                }
            }
        }
        int count = 0;
        for(int i = 2; i < primes.length; i++) {
            if(primes[i]) {
                count++;
            }
        }
        System.out.println("\ncount: " + count);
    }

    /**
     * 歐拉篩選法
     * 在埃氏篩法的基礎(chǔ)上牡昆，讓每個(gè)合數(shù)只被它的最小質(zhì)因子篩選一次姚炕，以達(dá)到不重復(fù)的目的
     * 時(shí)間復(fù)雜度為：O(n)
     */
    public void primeNumber5(int n) {

        // 用來(lái)存放質(zhì)數(shù)
        int[] set = new int[n + 1];
        // 用來(lái)標(biāo)記合數(shù)
        boolean[] bol = new boolean[n + 1];

        int count = 0;
        for (int i = 2; i < n; i++) {
            // 如果 i 是素?cái)?shù) 存放在 set 里
            if (!bol[i]){
                // count 統(tǒng)計(jì)的目前 質(zhì)數(shù)的個(gè)數(shù) 正好可以用這個(gè) count 將 質(zhì)數(shù)順序的存放在 set 集合中
                set[count] = i;
                count++;
            }

            /*
             根據(jù) 合數(shù)的定義(一個(gè)合數(shù)肯定是若干素?cái)?shù)的乘積) 所以素?cái)?shù)的倍數(shù)一定是合數(shù)
             所以 用 這個(gè)素?cái)?shù), 乘以現(xiàn)在已知的其他素?cái)?shù), 那么得到的會(huì)是一個(gè)個(gè)合數(shù) 在 bol 中標(biāo)記
              */
            for (int j = 0; j < count; j++) {
                // 排除掉 超過(guò) n 的合數(shù)
                if (i * set[j] > n) break;
                // 為合數(shù)在 bol 中做標(biāo)記
                bol[i*set[j]] = true;
                if (i%set[j] == 0 ) break;
            }

        }


        for (int i : set) {
            System.out.println(i);
        }
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        System.out.println("Find all prime numbers <= n，enter n：");
        int n = input.nextInt();

        long start = 0;
        long end = 0;

        start = System.currentTimeMillis();
        new PrimeNumber().primeNumber1(n);
        end = System.currentTimeMillis();

        System.out.printf("primeNumber1 所用時(shí)間為(單位毫秒)：%d\n", end - start);

        start = System.currentTimeMillis();
        new PrimeNumber().primeNumber2(n);
        end = System.currentTimeMillis();

        System.out.printf("primeNumber2 所用時(shí)間為(單位毫秒)：%d\n", end - start);

        start = System.currentTimeMillis();
        new PrimeNumber().primeNumber3(n);
        end = System.currentTimeMillis();

        System.out.printf("primeNumber3 所用時(shí)間為(單位毫秒)：%d\n", end - start);

        start = System.currentTimeMillis();
        new PrimeNumber().primeNumber4(n);
        end = System.currentTimeMillis();

        System.out.printf("primeNumber4 所用時(shí)間為(單位毫秒)：%d\n", end - start);

        start = System.currentTimeMillis();
        new PrimeNumber().primeNumber5(n);
        end = System.currentTimeMillis();

        System.out.printf("primeNumber5 所用時(shí)間為(單位毫秒)：%d\n", end - start);
    }
}

原文：https://blog.csdn.net/XlxfyzsFdblj/article/details/81149668 

n = 2000000

Find all prime numbers <= n，enter n：
2000000

count: 148933
primeNumber1 所用時(shí)間為(單位毫秒)：294368

count: 148933
primeNumber2 所用時(shí)間為(單位毫秒)：855

count: 148933
primeNumber3 所用時(shí)間為(單位毫秒)：165

count: 148933
primeNumber4 所用時(shí)間為(單位毫秒)：71

count: 148933
primeNumber5 所用時(shí)間為(單位毫秒)：31