笨鸟

天道酬勤，思者常新；博观约取，厚积薄发；心如止水，气贯长虹；淡泊明志，宁静致远。
posts - 10, comments - 0, trackbacks - 0, articles - 1

问题10－求小于2000000的质数之和

Posted on 2010-11-23 17:22 ClumsyBird 阅读(390) 评论(0)  编辑  收藏 所属分类: 一些问题－projecteuler
    问题描述如下：
        “10以下的质数之和为2+3+5+7＝17，求2000000以下的质数之和？”

    此问题相对比较简单，在前面的问题中已经给出质数判断的方法，具体代码如下：
/**
     * 判断是否是素数
     * 
     * @param n
     * @return
     */
    public static boolean isPrimeNumber(int n) {
        if (n < 2) {
            return false;
        }
        double max = Math.sqrt(n);
        for (int i = 2; i <= max; i++) {
            if (n % i == 0) {
                return false;

            }
        }
        return true;
    }

    问题的实现方法如下：
/**
     * 小于n的质数之和
     * @param n
     * @return
     */
    private static Long getPrimeNumberSum(int n) {
        int i = 2;
        Long sum = 2L;
        while (i <= n) {
            if (AlgorithmUtil.isPrimeNumber(++i)) {
                sum += i;
            }
        }
        return sum;
    }

    即可得到答案142913828922。

    稍稍优化一下，
    /**
     * 小于n的质数之和
     * 
     * @param n
     * @return
     */
    private static Long getPrimeNumberSum(int n) {
        int i = 5;
        Long sum = 5L;//由于2，3都是质数，初始值为5
        while (i <= n) {
            if (AlgorithmUtil.isPrimeNumber(i += 2)) {//质数 不能被2整除
                sum += i;
            }
            if (i <= n && AlgorithmUtil.isPrimeNumber(i += 4)) {//不能被3整除
                sum += i;
            }
        }
        return sum;
    }
    还可以通过埃拉托斯特尼筛法（http://zh.wikipedia.org/zh-cn/%E5%9F%83%E6%8B%89%E6%89%98%E6%96%AF%E7%89%B9%E5%B0%BC%E7%AD%9B%E6%B3%95）来质数之和。

    请不吝赐教。
    @anthor ClumsyBird

-----------------------------
博观约取，厚积薄发


只有注册用户登录后才能发表评论。
网站导航: