它应该多少时间来查找所有质数低于200万的款项？ [英] How much time should it take to find the sum of all prime numbers less than 2 million?

问题描述

我试图解决这个项目欧拉问题。我实现了欧拉的筛作为Java中的辅助类。它的工作原理pretty的良好的小数目。但是，当我输入2万元为限不返回答案。我使用NetBeans IDE。我等了很多很多小时一次，但它仍然没有打印答案。当我停止运行code，它给了以下结果。

  

Java结果：2147483647
  建立   成功（总时间：2097分钟   43秒）

这个答案是不正确。即使等了这么多时间，这是不正确的。而同样code返回较小的范围正确的答案。

欧拉筛具有此页的钮给出一个很简单的算法中。

我的实现是这样的：

 包的支持;

进口的java.util.ArrayList;
进口的java.util.List;

/ **
 *
 * @author管理
 * /
公共类SieveOfEuler {
    INT UPPERLIMIT;
    名单＆LT;整数GT;质数;

    公共SieveOfEuler（INT UPPERLIMIT）{
        this.upperLimit = UPPERLIMIT;
        primeNumbers =新的ArrayList＆LT;整数GT;（）;
        的for（int i = 2; I＆LT; = UPPERLIMIT;我++）
            primeNumbers.add（ⅰ）;
        generatePrimes（）;
    }

    私人无效generatePrimes（）{
        INT currentPrimeIndex = 0;
        INT currentPrime = 2;
        而（currentPrime＆LT; =的Math.sqrt（UPPERLIMIT））{
            ArrayList的＆LT;整数GT; toBeRemoved =新的ArrayList＆LT;整数GT;（）;
            的for（int i = currentPrimeIndex; I＆LT; primeNumbers.size（）;我++）{
                INT乘数= primeNumbers.get（我）;
                toBeRemoved.add（currentPrime *乘数）;
            }

            对于（整数i：toBeRemoved）{
                primeNumbers.remove（ⅰ）;
            }

            currentPrimeIndex ++;
            currentPrime = primeNumbers.get（currentPrimeIndex）;
        }
    }

    公开名单getPrimes（）{
        返回primeNumbers;
    }

    公共无效displayPrimes（）{
        对于（双I：primeNumbers）
            的System.out.println（ⅰ）;
    }
}
 

我很困惑！我的问题是

1）为什么用了这么多的时间？有什么错在我在做什么？

请建议的方式对于提高我的编码风格，如果你发现了什么。

问题更新时间：

下面是code，我在那里计算计算素数之和：

 包projecteuler;

进口java.io.IOException异常;
进口java.math.BigInteger的;
进口的java.util.ArrayList;
进口java.util.logging.Level中;
进口java.util.logging.Logger中;
进口support.Sie​​veOfEuler;

/ **
 *
 * @author管理
 * /
公共类Problem10 {
    私人诠释UPPERLIMIT;
    私人的BigInteger sumOfPrimes;
    公共无效getInput（）{
        尝试 {
            的System.out.println（输入上限）;
            UPPERLIMIT =的Integer.parseInt（br.readLine（））;
        }赶上（IOException异常前）{
            。Logger.getLogger（Problem10.class.getName（））日志（Level.SEVERE，空，前）;
        }
    }

    公共无效的execute（）{
        的BigInteger总和=新的BigInteger（0）;
        SieveOfEuler SOE =新SieveOfEuler（UPPERLIMIT）;
        ArrayList的＆LT;整数GT; primeNumbers =（的ArrayList＆其中;整数＆GT）soe.getPrimes（）;
        对于（INT I：primeNumbers）{
            总和= sum.add（新的BigInteger（Integer.toString（ⅰ）））;
        }
        的System.out.println（总和）;
    }

    公共无效printOutput（）{
       //System.out.println(sumOfPrimes）;
    }
}
 

解决方案

这是你的筛是如此缓慢的原因是你已经取得了根本性的错误。该 primeNumbers 应该是布尔数组，而不是一个列表。当您完成时， primeMumbers [I] 将真素数和假复合材料。

这也是为什么它使这么大的区别：

• 设置或阵清除标志 O（1）;即每运行一个小的固定时间。
• 从的ArrayList 是 O（N），其中 N 是列表的大小...和的非常大的。
• 在每个 ArrayList.remove（...）操作必须的搜索的名单。如果该值已经不存在（因为你已经删除它），删除操作有看的每次的其余列表元素...直到他们到〜2万... - 每次它被调用。
• 当 ArrayList.remove（...）找到一个元素，它的元素一个指标，左侧是支持数组后复制所有剩余的元素中删除。同样，你要复制可达〜2万条......每次你删除一个。

我期望Erasothenes的执行情况良好筛，以便能够计算所有质数在几秒钟不到2万元。

I was trying to solve this Project Euler Question. I implemented the sieve of euler as a helper class in java. It works pretty well for the small numbers. But when I input 2 million as the limit it doesn't return the answer. I use Netbeans IDE. I waited for a lot many hours once, but it still didn't print the answer. When I stopped running the code, it gave the following result

Java Result: 2147483647
BUILD SUCCESSFUL (total time: 2,097 minutes 43 seconds)

This answer is incorrect. Even after waiting for so much time, this isn't correct. While the same code returns correct answers for smaller limits.

Sieve of euler has a very simple algo given at the botton of this page.

My implementation is this:

package support;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * @author admin
 */
public class SieveOfEuler {
    int upperLimit;
    List<Integer> primeNumbers;

    public SieveOfEuler(int upperLimit){
        this.upperLimit = upperLimit;
        primeNumbers = new ArrayList<Integer>();
        for(int i = 2 ; i <= upperLimit ; i++)
            primeNumbers.add(i);
        generatePrimes();
    }

    private void generatePrimes(){
        int currentPrimeIndex = 0;
        int currentPrime = 2;
        while(currentPrime <= Math.sqrt(upperLimit)){
            ArrayList<Integer> toBeRemoved = new ArrayList<Integer>();
            for(int i = currentPrimeIndex ; i < primeNumbers.size() ; i++){
                int multiplier = primeNumbers.get(i);
                toBeRemoved.add(currentPrime * multiplier);
            }

            for(Integer i : toBeRemoved){
                primeNumbers.remove(i);
            }

            currentPrimeIndex++;
            currentPrime = primeNumbers.get(currentPrimeIndex);
        }
    }

    public List getPrimes(){
        return primeNumbers;
    }

    public void displayPrimes(){
        for(double i : primeNumbers)
            System.out.println(i);
    }
}

I am perplexed! My questions is

1) Why is it taking so much time? Is there something wrong in what I am doing?

Please suggest ways for improving my coding style, if you find something wrong.

Question Updated:

Here is the code, where I calculate the sum of the the calculated prime numbers:

package projecteuler;

import java.io.IOException;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.logging.Level;
import java.util.logging.Logger;
import support.SieveOfEuler;

/**
 *
 * @author admin
 */
public class Problem10 {
    private int upperLimit;
    private BigInteger sumOfPrimes;
    public void getInput() {
        try {
            System.out.println("Enter the upper limit");
            upperLimit = Integer.parseInt(br.readLine());
        } catch (IOException ex) {
            Logger.getLogger(Problem10.class.getName()).log(Level.SEVERE, null, ex);
        }
    }

    public void execute() {
        BigInteger sum = new BigInteger("0");
        SieveOfEuler soe = new SieveOfEuler(upperLimit);
        ArrayList<Integer> primeNumbers = (ArrayList<Integer>)soe.getPrimes();
        for(int i : primeNumbers){
            sum = sum.add(new BigInteger(Integer.toString(i))) ;
        }
        System.out.println(sum);
    }

    public void printOutput() {
       //System.out.println(sumOfPrimes);
    } 
}

解决方案

The reason that your Sieve is so slow is that you have made a fundamental mistake. The primeNumbers should be an array of booleans, not a List. When you are finished, the value of primeMumbers[i] will be true for prime numbers and false for composites.

Here's why it makes such a big difference:

• Setting or clearing a flag in array is O(1) ; i.e. a small constant time per operation.
• Removing an element from an ArrayList is O(N) where N is the size of the list ... and very large.
• Each ArrayList.remove(...) operation has to search the list. If the value is no longer there (because you've already removed it), the remove operation has to look at every remaining element in the list ... up to ~2 million of them ... each time it is called.
• When ArrayList.remove(...) finds an element, it removes it by copying all remaining elements after the element one index to the left in the backing array. Again, you are copying up to ~2 million entries ... each time you remove one.

I'd expect a well implemented Sieve of Erasothenes to be able to calculate all prime numbers less than 2 million in a few seconds.

这篇关于它应该多少时间来查找所有质数低于200万的款项？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！