求[1,n]之间的所有素数 博客分类： algorithm AlgorithmJava

package primenumber.s1;

/**
 * Created by Lanxiaowei
 * Craated on 2016/12/10 21:53
 * 求出[1,n]之间的所有素数
 * 最原始的做法
 */
public class TestPrimeNumber {
    //统计遍历的次数
    private static int opsNum = 0;

    public static void main(String[] args) {
        //假设求1-100以内的所有素数
        int n = 100;
        for(int i=2; i < n; i++) {
            boolean isPrime = isPrime(i);
            //如果是素数，则打印出来
            if(isPrime) {
                System.out.println(i);
            }
        }
        System.out.println("Total loop times:" + opsNum);
    }

    /**
     * 判断是否为素数
     * @param n    待判断的数字
     * @return
     */
    private static boolean isPrime(int n) {
        //若传入的数字n小于2,则直接return false,因为最小的素数为2
        if(n < 2) {
            return false;
        }
        //从2遍历到n-1
        for(int i = 2; i < n; ++i) {
            opsNum++;
            //如果发现能被其中任意一个数整除,那么说明数字n不是素数
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
}

 

package primenumber.s2;

/**
 * Created by Lanxiaowei
 * Craated on 2016/12/10 21:53
 * 求出[1,n]之间的所有素数
 */
public class TestPrimeNumber {
    //统计遍历的次数
    private static int opsNum = 0;
    public static void main(String[] args) {
        //假设求1-100以内的所有素数
        int n = 100;
        for(int i=2; i < n; i++) {
            boolean isPrime = isPrime(i);
            //如果是素数，则打印出来
            if(isPrime) {
                System.out.println(i);
            }
        }
        System.out.println("Total loop times:" + opsNum);
    }

    /**
     * 判断是否为素数
     * @param n    待判断的数字
     * @return
     */
    private static boolean isPrime(int n) {
        //若传入的数字n小于2,则直接return false,因为最小的素数为2
        if(n < 2) {
            return false;
        }
        if(n == 2) {
            return true;
        }
        //如果传入的数字是偶数,那么一定不是素数
        if(n%2==0) {
            return false;
        }
        //从3开始遍历剩下的所有奇数
        for(int i = 3; i < n; i += 2) {
            opsNum++;
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
}

 

package primenumber.s3;

/**
 * Created by Lanxiaowei
 * Craated on 2016/12/10 21:53
 * 求出[1,n]之间的所有素数
 * 定理: 如果n不是素数, 则n有满足1< d<=sqrt(n)的一个因子d.
 * 证明: 如果n不是素数, 则由定义n有一个因子d满足1< d< n.
 * 如果d > sqrt(n), 则 1/d <= √n ==> n/d <= √n
 * 则n/d是满足1 < n/d <= sqrt(n)的一个因子.
 */
public class TestPrimeNumber {
    //统计遍历的次数
    private static int opsNum = 0;
    public static void main(String[] args) {
        //假设求1-100以内的所有素数
        int n = 100;
        for(int i=2; i < n; i++) {
            boolean isPrime = isPrime(i);
            //如果是素数，则打印出来
            if(isPrime) {
                System.out.println(i);
            }
        }
        System.out.println("Total loop times:" + opsNum);
    }

    /**
     * 判断是否为素数
     * @param n    待判断的数字
     * @return
     */
    private static boolean isPrime(int n) {
        //若传入的数字n小于2,则直接return false,因为最小的素数为2
        if(n < 2) {
            return false;
        }
        if(n == 2) {
            return true;
        }
        //如果传入的数字是偶数,那么一定不是素数
        if(n%2==0) {
            return false;
        }
        //遍历从3到根号n之间的所有奇数
        for(int i = 3; i*i <= n; i += 2) {
            opsNum++;
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
}

 

package primenumber.s4;

/**
 * Created by Lanxiaowei
 * Craated on 2016/12/10 21:53
 * 求出[1,n]之间的所有素数
 * 定理: 若A = B * C且B <= C,B是能整除A的最小数字,那么B一定是素数
 * 证明: 假设B不是素数,那么对于B一定存在这样的等式B=P*M,此时P肯定小于B,
 *      B能整除A,那么P也一定能够整除A,那么说明B一定不是能整除A的最小数字,
 *      然而此时推理与题设提交相矛盾,由此证明"B不是素数"这个假设不成立即B一定是素数,
 *      从而定理得以证明.
 *      另外,根据题设中的条件: A = B * C且B <= C,我们可以得出:
 *      B * B <= A ==> B <= √A
 */
public class TestPrimeNumber {

    public static void main(String[] args) {
        //假设求1-100以内的所有素数
        int n = 100;
        boolean[] result = getPrimes(n);
        for(int i=2; i < n; i++) {
            boolean isPrime = result[i - 1];
            //如果是素数，则打印出来
            if(!isPrime) {
                System.out.println(i);
            }
        }
    }

    /**
     * 判断是否为素数
     * @param n    待判断的数字
     * @return
     */
    private static boolean isPrime(int n) {
        boolean[] result = getPrimes(n);
        return !result[n-1];
    }

    /**
     * 标记[1,n]之间的所有素数
     * @param n
     * @return
     */
    private static boolean[] getPrimes(int n) {
        //统计遍历的次数
        int opsNum = 0;
        //使用一个数组标记[1,n]之间的每个数字是否为素数,false表示素数,true表示合数
        boolean[] isPrimes = new boolean[n];
        //这里的变量i即上面定理中的B,之所以是i * i < n,是由我们推断出的结论:B <= √A演化而来
        for(int i=2; i * i <= n; i++) {
            //若为合数,则直接跳过
            if(isPrimes[i - 1]) {
                continue;
            }
            // i * j <= n即B * C不能大于A,由A = B * C可知
            for(int j = 2; i * j <= n; j++) {
                //此时i * j一定是合数
                isPrimes[i * j - 1] = true;
                //统计遍历次数,主要是为了了解算法的性能
                opsNum++;
            }
        }
        System.out.println("Total loop times:" + opsNum);
        return isPrimes;
    }
}

 

package primenumber.s5;

/**
 * Created by Lanxiaowei
 * Craated on 2016/12/10 21:53
 * 求出[1,n]之间的所有素数[最高效的算法,算法复杂度O(n)]
 * 定理: 拿已知的素数列表去过滤合数,那么能够保证被过滤掉的合数有且只被过滤一次
 */
public class TestPrimeNumber {

    public static void main(String[] args) {
        //假设求1-100以内的所有素数
        int n = 100;
        boolean[] result = getPrimes(n);
        for(int i=2; i < n; i++) {
            boolean isPrime = result[i - 1];
            //如果是素数，则打印出来
            if(!isPrime) {
                System.out.println(i);
            }
        }
    }

    /**
     * 判断是否为素数
     * @param n    待判断的数字
     * @return
     */
    private static boolean isPrime(int n) {
        boolean[] result = getPrimes(n);
        return !result[n-1];
    }

    /**
     * 标记[1,n]之间的所有素数
     * @param n
     * @return
     */
    private static boolean[] getPrimes(int n) {
        //统计遍历的次数
        int opsNum = 0;
        //使用一个数组标记[1,n]之间的每个数字是否为素数,false表示素数,true表示合数
        boolean[] isPrimes = new boolean[n];
        //目前已知的素数
        int[] primeList = new int[n];
        //目前已知素数列表索引
        int p = 0;
        for(int i=2; 2 * i <= n; i++) {
            //若为素数,则记录到目前已知的素数数组中
            if(!isPrimes[i - 1]) {
                primeList[p++] = i;
            }
            //遍历目前已知的素数来过滤合数
            for(int j = 0; j < p; j++) {
                if(i * primeList[j] <= n) {
                    // i * primeList[j]一定是合数,因为已知primeList[j]是素数,而i > 1,因此得以证明i * primeList[j]一定是合数.
                    isPrimes[i * primeList[j] - 1] = true;
                    //统计遍历次数,主要是为了了解算法的性能
                    opsNum++;
                }

                // 如果i不是一个素数
                if(i % primeList[j] == 0) {
                    break;
                }
            }
        }
        System.out.println("Total loop times:" + opsNum);
        return isPrimes;
    }
}