Что такое эффективный способ быстрого добавления тысяч чисел?

Question

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

Что такое эффективный способ быстрого добавления тысяч чисел?

Сторона примечания: Я читал об модульной арифметике, но я не могу ее обворачивать. Не уверен, что это может быть полезно для этой ситуации.

Я пытаюсь получить сумму каждого простого числа ниже 2 000 000. Вот мой код до сих пор:

public class Problem10 { 
    public static void main (String[] args) { 
     long sum = 0L; 

     for(long i = 1L; i < 2000000; i++) { 
      if(isPrimeNumber((int)i)) { 
       sum += i; 
      } 
     } 
     System.out.println(sum); 
    } 

    public static boolean isPrimeNumber(int i) { 
     int factors = 0; 
     int j = 1; 

     while (j <= i) { 
      if (i % j == 0) { 
       factors++; 
      } 
      j++; 
     } 
     return (factors == 2); 
    } 
} 

Answer 1

Вы можете заменить свой метод isPrimeNumber(), чтобы ускорить его.

public static boolean isPrimeNumber(int i) { 
    if (i==2) return true; 
    if (i==3) return true; 
    if (i%2==0) return false; 
    if (i%3==0) return false; 

    int j = 5; 
    int k = 2; 

    while (j * j <= i) { 
     if (i % j == 0) return false; 
     j += k ; 
     k = 6 - k; 

    } 
    return true; 
} 

Answer 2

Это выглядит как домашнее задание, так что я не собираюсь давать вам решение в коде. Самое меньшее, что вы можете сделать, это код сам.

---

В коде isPrimeNumber() это то, что занимает большую часть времени, если я должен был догадаться, я бы сказал, 90-99% из них. То, что вы можете сделать, чтобы сделать это быстрее, - это реализовать Sieve of Eratosthenes.

Для начала создайте массив, который будет содержать все простые числа . Вы должны запустить его с помощью одного значения: 2. Чтобы найти больше простых чисел, выполните итерацию через каждое целое число от 3 до наивысшего числа, которое вы хотите. Для каждого из этих чисел проверьте, делится ли это число на любое из простых чисел в вашем массиве. Если следующее простое число в вашем массиве больше i/2, вы знаете, что i является простым, и вы можете добавить его в свой массив.

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

Есть два способа сделать это. Один из них - просто использовать ArrayList или LinkedList и добавлять числа по мере необходимости. Другой - создать массив, который является таким же большим или большим, чем вам нужно. Как уже упоминалось here, число простых чисел, равных или меньших, чем п меньше (n/log(n)) * (1 + 1.2762/log(n)), если п больше, чем 598. Если п меньше, чем 598, вы можете просто создать массив длиной 109.

---

Что касается вопроса в заголовке «Что такое эффективный метод для добавления тысяч чисел быстро?», Единственное, что я могу придумать, - это многопоточность. Создайте массив всех чисел, которые вы хотите суммировать, а затем много потоков суммируют разные части массива. После этого суммируйте все результаты от каждого потока. Этот метод, вероятно, будет только заметно быстрее при суммировании огромного количества чисел, например. сотни тысяч или миллионы.