Сколько времени нужно, чтобы найти сумму всех простых чисел менее 2 миллионов?

Question

Я пытался решить эту проблему Project Euler Question .Я реализовал сито Euler в качестве вспомогательного класса в Java.Это работает довольно хорошо для небольших номеров.Но когда я ввожу 2 миллиона как предел, он не возвращает ответ.Я использую Netbeans IDE.Я ждал много часов, но ответа так и не было.Когда я остановил выполнение кода, он дал следующий результат

Результат Java: 2147483647
BUILD SUCCESSFUL (общее время: 2 097 минут 43 секунды)

Этот ответэто неверно.Даже после ожидания так много времени, это не правильно.Хотя тот же код возвращает правильные ответы для меньших пределов.

Сито Эйлера имеет очень простой алгоритм, данный у основания страницы .

Моя реализация такова:

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);
    }
}

Я озадачен!Мои вопросы

1) Почему это занимает так много времени?Что-то не так в том, что я делаю?

Пожалуйста, предложите способы улучшить мой стиль кодирования, если вы обнаружите что-то неправильное.

Вопрос обновлен:

Вот кодгде я вычисляю сумму вычисленных простых чисел:

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);
    } 
}

Answer 1

Причина, по которой ваше Сито так медленно, в том, что вы совершили фундаментальную ошибку. primeNumbers должен быть массивом логических значений, а не List. Когда вы закончите, значение primeMumbers[i] будет true для простых чисел и false для композитов.

Вот почему это так важно:

• Установка или очистка флага в массиве O(1); т.е. небольшое постоянное время на операцию.
• Удаление элемента из ArrayList - это O(N), где N - это размер списка ... и очень большой .
• Каждая ArrayList.remove(...) операция должна искать список. Если значение больше не существует (потому что вы уже удалили его), операция удаления должна просмотреть каждый оставшийся элемент в списке ... до ~ 2 миллионов из них ... каждый время это называется.
• Когда ArrayList.remove(...) находит элемент, он удаляет его, копируя все оставшиеся элементы после индекса на один элемент слева в массиве поддержки. Опять же, вы копируете до ~ 2 миллионов записей ... каждый раз, когда удаляете одну.

Я ожидаю, что хорошо реализованное Sieve of Erasothenes сможет вычислить все простые числа менее 2 миллионов за несколько секунд.

Answer 2

Чтобы дать ответ на вопрос в названии этой темы: это то, что говорит веб-сайт проекта Эйлера: http://projecteuler.net/index.php?section=about

Я написал свою программу, но если на это уйдут дни,на ответ?Точно нет!Каждая проблема была разработана в соответствии с «правилом одной минуты» , что означает, что, хотя для разработки успешного алгоритма с более сложными задачами может потребоваться несколько часов, эффективная реализация позволит получить решениена компьютере со скромным питанием менее чем за одну минуту.

; -)

Answer 3

for(int i = currentPrimeIndex ; i < primeNumbers.size() ; i++){
    int multiplier = primeNumbers.get(i);
    toBeRemoved.add(currentPrime * multiplier);
}

На первом шаге генерируется ArrayList из 2 миллионов кратных 2 (toBeRemoved).

Затем он перебирает toBeRemoved, сканируя весь массив из 2 миллионов простых чисел-кандидатов один раз для каждой записи в toBeRemoved.Половина значений в toBeRemoved не может быть в primeNumbers, потому что они слишком большие.Каждое удаление приводит к тому, что каждое значение с большим индексом, чем удаляемое, сдвигается вниз на одну позицию.

Я думаю, что это основной источник неэффективности.Обычный способ реализовать сито Эратосфена - создать массив из 2 миллионов логических значений, изначально все верно.Когда i определено как не простое, установите possibly_prime[i] в false.Чтобы найти следующее простое число, отсканируйте вперед в поисках значения true.Чтобы получить список всех простых чисел в конце, выполните итерацию массива, записывающего индекс каждого значения true.Вы должны сделать почти то же самое для сита Эйлера.

Вам не нужно будет оптимизировать этот процесс для простых чисел до 2 миллионов.

Answer 4

Некоторые очевидные ошибки:

while(currentPrime <= Math.sqrt(upperLimit))

Квадратный корень рассчитывается на каждом шаге (если не оптимизировано компилятором).Вы должны рассчитать его один раз и сохранить результат.

currentPrimeIndex++;

Вы должны хотя бы выполнить очевидную оптимизацию и проверять только нечетные числа.Вы уже знаете, что четные числа не являются простыми числами.Это должно сократить ваше время в два раза.

Кроме того, вы используете метод грубой силы, чтобы найти простые числа.Это будет медленно для больших верхних пределов.Вы должны использовать лучший алгоритм для своего поиска - вы сможете найти больше информации в Интернете, однако я не знаю, разрешено ли это в духе Project Euler.

Answer 5

import java.util.*;

public class PrimeSum
{
    public static int isPrime(int num)
    {
        int sum = 0;
        int factor = 1;
        while(factor <= num)
        {
            if(num % factor != 0)
            {
                sum += factor;
                factor ++;
            }
            else
            {
                factor ++;
            }
        }
        return sum;
    }

    public static void main(String[] args)
    {
        System.out.println("The program gets the sum of all prime numbers.");

        Scanner scan = new Scanner(System.in);

        System.out.print("Enter a number: ");
        int num = scan.nextInt();

        int sum = isPrime(num);

        System.out.println(sum);
    }
}

Answer 6

Вот решение с использованием простого сита Эратосфена:

function sumPrimes(n)
    sum, sieve := 0, makeArray(2..n, True)
    for p from 2 to n
        if sieve[p]
            sum := sum + p
            for i from p*p to n step p
                sieve[i] := False
    return sum

Я кодирую это решение на Python здесь , где это занимает одну четверть секунды. Если вы заинтересованы в программировании с простыми числами, я скромно рекомендую эссе в моем блоге.

Answer 7

Даже без решета этот вопрос решается менее чем за 1 секунду.Чтобы проверить, является ли число простым или нет: http://www.parseexception.com/how-to-check-whether-a-number-is-prime-or-not/

Выполните эту операцию для всех чисел и сложите их.

Answer 8

1. Является ли list правильный тип для этого? Набор будет работать намного лучше во время remove(obj). В вашем случае попробуйте BitSet.

2. Сначала вы создаете (длинный) список элементов для удаления, а затем удаляете их по отдельности. Почему бы просто не удалить их?

3. Результат не помещается в int.

Answer 9

while (currentPrime <= Math.sqrt (upperLimit)) // Уменьшает сложность и еще одно замечание: сумма не <strong>int .происходит переполнение

Если это поможет вам, вы посмотрите на мое решение.Вот мое решение

public static boolean isPrime(int i) { // general isPrime method
      if (i < 2) {
         return false;
      } else if (i % 2 == 0 && i != 2) {
          return false;
      } else {
           for (int j = 3; j <= Math.sqrt(i); j = j + 2) {
               if (i % j == 0) {
                  return false;
                }
           }
      }

  return true;
 }

    public static boolean isPrimeForOdd(int i){ // only for odds
        for (int j = 3; j <= Math.sqrt(i); j = j + 2) {
             if (i % j == 0) {
                return false;
              }
        }

      return true;
     }

 public static long sumOfPrimes(int n) {
    long sum = 2;

    for (int i = 3; i < n; i += 2) {
          if (isPrimeForOdd(i)) {
              sum += i;
          }
    }

    return sum;
 }

 public static void main(String[] args) throws ParseException {
      System.out.println(sumOfPrimes(2000000));
 }