Как улучшить алгоритм простой суммы?

Question

Я написал код, который возвращает сумму всех простых чисел, значения которых составляют менее 2 миллионов. Но на это уходит огромное время (дождался 30 минут ответа).

Может ли кто-нибудь предложить, как сделать алгоритм более эффективным?

public static void main(String[] args){ 

    int i,primeNum=1,sumPrime=0,c=0; 
    while (primeNum<2000000){ 
      int factors=0; 
      for(i=1;i<=primeNum;i++){ 
       if((primeNum%i)==0) { 
        factors++; // total number of factors     
       } 
      }    
      if(factors==2){ 
       if(primeNum<2000000){ 
        sumPrime=primeNum+c; 
        c=sumPrime; 
       } 
       System.out.println(primeNum); 
      } 

      primeNum++; 

     } 
     System.out.println(sumPrime); 
    } 

Answer 1

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

public static void main(String[] args) { 
    //you know 2 is the only even prime. 
    int sum = 2; 
    for (int i = 3; i <= 2000000; i++) { 
     boolean prime = isPrime(i); 
     if(prime){ 
      sum+=i; 
     } 
    } 
    System.out.println("Sum = " + sum); 
} 

/* 
* we know 2 is the “oddest” prime – it happens to be the only even prime 
* number. Because of this, we need only check 2 separately, then traverse 
* odd numbers up to the square root of n 
*/ 
public static boolean isPrime(int n) { 
    // check if n is a multiple of 2 
    if (n % 2 == 0) 
     return false; 
    // if not, then just check the odds 
    for (int i = 3; i * i <= n; i += 2) { 
     if (n % i == 0) 
      return false; 
    } 
    return true; 
} 

Answer 2

Для начала:

• ли петля for(i=1;i<=primeNum;i++){ должны бежать primeNum или, может быть, просто квадратный корень из primeNum?
• i должен быть увеличен на 1 или более эффективен?
• ...

Answer 3

Ваш алгоритм действительно неэффективна, для алгоритмов вычисления простых чисел выглядят here. Подведение итогов, если у вас их есть, не должно быть проблемой.

Answer 4

Уменьшить использование условий if. Это замедляет ваш код. Попробуйте использовать тройные операторы, если это возможно, если это влияет на вашу скорость, даже если это не рекомендуется в java 1.5.

Попробуйте это решение:

if((factors==2)&&(primeNum<2000000)) 

вместо повторной, если условия и размещать какие-либо различия.

Answer 5

Я не обеспечит вам полный ответ, в качестве цели проекта Эйлера (где я предполагаю, у вас есть эта проблема), это думать о вещах и придумывать решения.

Во всяком случае, я оставлю некоторые шаги, которые помогут вам в правильном направлении:

• Разбейте свой код на два метода:
  • Эратосфена решето (http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes), который является довольно тривиально, и будет вернет вам список всех простых чисел под 2M.
  • Метод, который просто суммирует все значения, возвращаемые ситом.

Это будет очень эффективным, если вы реализуете сито правильно, он должен принести вниз время выполнения на пару секунд.

Answer 6

проверка sieve of Atkin алгоритм. Это оптимизированная версия древнего sieve of Eratosthenes.

Answer 7

Есть несколько вещей:

1. Если вы хотите, чтобы определить более одного простого алгоритма решета гораздо лучше. (Google для сита Эратосфена, а затем подведите итог).

2. Даже при использовании наивного алгоритма, как вы это делаете, есть несколько улучшений можно:

   1. Думает об этом: кроме первого, даже премьера, все остальные нечетные, так что вы не должны делать/primeNumber++ в вашей петле, но еще primeNumber+=2 (и на самом деле начать цикл не с 1). [Runtime halfed]

   2. Вы проверяете свой внутренний цикл для всех чисел, меньших, чем основной кандидат, если они являются его фактором. Там вы также можете пропустить все четные числа (и увеличивать всегда на два). [Runtime почти наполовину].

   3. В вашей внутренней петле вы можете сэкономить еще больше. Вам не нужно проверять весь номер < prime, но только до < sqrt (prime). Потому что, когда число делит простое, всегда должны быть два фактора, и один из них должен быть меньше (или равен) квадратному корню. [Runtime "roototed"]

   4. Вы не хотите, чтобы факторы простого числа, вы только хотите знать, является ли число простым или нет. Поэтому, когда вы знаете, что это не просто, НЕ продолжайте его тестировать (т.е. выходите из цикла, когда у вас есть первый фактор (чтобы сделать это проще, вы НЕ должны тестировать 1 и сам номер) - это спасет вас огромное количество времени. [время выполнение еще более снижаются.]

Так с этим советами даже ваш наивный подход без решета приведет к выполнению менее 2 протоколируется (SQRT (15/4)) .

Answer 8

Эта часть очень innefficent: -

for(i=1;i<=primeNum;i++){ 
    if((primeNum%i)==0) { 
    factors++; // total number of factors     
    } 
}  

Подсчитывает общее количество факторов. Поскольку все, что вас интересует, - это число, простое или нет, количество факторов не требуется. Тест должен быть, если есть фактор, который не является 1 или проверенным числом. Таким образом, вы можете это сделать: -

boolean is_prime = true; 
// start at 3 as 1 is always a factor and even numbers above 2 are definately not prime, terminate at n-1 as n is also a factor 
for(i=3;i<primeNum;i+=2){ 
    if((primeNum%i)==0) { 
    is_prime = false; 
    break; 
    } 
} 

Это теперь более эффективно для не простых чисел. Для простых чисел это слишком много, факторы попадают в пары: если a.b == c, то a < = sqrt (c) и b> = sqrt (c), поэтому цикл может безопасно завершаться в sqrt (primeNum). Вы можете вычислить sqrt (primeNum) перед циклом, но для этого обычно требуется использование функций с плавающей запятой. Вместо этого или заканчивая при i> sqrt (primeNum), завершите цикл, когда i.i> primeNum. Вы также можете удалить умножение i.i и заменить его дополнительной переменной и несколькими добавками (слева в качестве упражнения для читателя).

Другим подходом является использование сита, как упомянуто другими, что является простым методом, когда существует фиксированный верхний предел для пространства поиска. Вы можете сделать версию, которая не имеет верхнего предела (размер памяти не выдерживает), но довольно сложно реализовать, поскольку для этого требуется немного динамического управления памятью. Не уверен, что простое сито будет быстрее, чем поиск факторов, поскольку вы будете бить память с помощью сита, который имеет большое влияние на скорость.

Answer 9

Эта функция суммирует штрихами менее п с помощью решета Эратосфена:

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

Я оставлю его вам перевести Java. Для n = 2000000, это должно выполняться через одну или две секунды.

Answer 10

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

void setup() { 
    for (int i = 1; i<2000000; i++) { 
    if (isPrime(i)) { 
     System.out.println(i); 
    } 
    } 
} 

boolean isPrime(int number) { 
    if (number < 2) return false; 
    if (number == 2) return true; 
    if (number % 2 == 0) return false; 
    for (int i = 3; (i*i)<=number; i+=2) { 
    if (number % i == 0) return false; 
    } 
    return true; 
} 

Answer 11

В Python, вы можете сделать это таким образом. По сравнению с некоторыми предыдущими решениями я стараюсь не менять вектор isPrime, как только я пересекаю $ \ sqrt {n} $

import math 
def sum_primes(nmax): 
    maxDivisor=int(math.floor(math.sqrt(nmax))) 
    isPrime=[False,False]+range(2,nmax+1) 

    for i in range(2,maxDivisor+1): 
     if isPrime[i] is not False: 
      for dummy in range(i*2,nmax+1,i): 
       isPrime[dummy]=False 

    print (sum(isPrime))