Вопрос по algorithm – Нахождение списка простых чисел в кратчайшие сроки

7

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

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

Ниже приведен мой код, могу ли я иметь лучшую версию того же самого?

 public static void main(String[] args) {
    for (int i = 2; i < 100000; i++) {
        if (checkMod(i)) {
            primes.add(i);
        }
    }
}

private static boolean checkMod( int num) {
    for (int i : primes){
        if( num % i == 0){
            return false;
        }
    }
    return true;
}
codereview.stackexchange.com j08691
Вы пытались искать на сайте? Существует множество вопросов по алгоритмам поиска простых чисел. Wooble
да я нашел решение здесьstackoverflow.com/questions/3808171/…   Но где-то это не очень хорошо объясняется, и я считаю, что это сложно :( dharam

Ваш Ответ

5   ответов
1

isPrime[100001] // - initially contains only '1' values (1,1,1 ... 1)
isPrime[0] = isPrime[1] = 0 // 0 and 1 are not prime numbers

primes.push(2); //first prime number. 2 is a special prime number because is the only even prime number.
for (i = 2; i * 2 <= 100000; i++) isPrime[i * 2] = 0 // remove all multiples of 2

for (i = 3; i <= 100000; i += 2) // check all odd numbers from 2 to 100000
    if (isPrime[i]) {
        primes.push(i); // add the new prime number to the solution
        for (j = 2; i * j <= 100000; j++) isPrime[i * j] = 0; // remove all i's multiples
    }

return primes

Я надеюсь, вы понимаете мои комментарии

0

@ Даниэль Фишер.

Реализация на C ++ из его объяснения:

#include<iostream>

using namespace std;

long* getListOfPrimeNumbers (long total)
{
  long * primes;
  primes = new long[total];
  int count = 1;
  primes[0] = 2;
  primes[1] = 3;
  while (count < total)
  {
    long composite_number = primes[count] + 2;
    bool is_prime = false;
    while (is_prime == false)
    {
      is_prime = true;
      for (int i = 0; i <= count; i++)
      {
        long prime = primes[i];
        if (prime * prime > composite_number)
        {
          break;
        }
        if (composite_number % prime == 0)
        {
          is_prime = false;
          break;
      }
      }
      if (is_prime == true)
      {
        count++;
        primes[count] = composite_number;
      }
      else
      {
        composite_number += 2;
    }
  }
  }
  return primes;
}

int main()
{
  long * primes;
  int total = 10;
  primes = getListOfPrimeNumbers(total);
  for (int i = 0; i < total; i++){
    cout << primes[i] << "\n";
  }
  return 0;
}
0

что простое число - это число, которое делится только на себя и на число 1 (без остатка). УвидетьСтатья в Википедии

При этом я не очень хорошо понимаю алгоритм во втором комментарии, но одним небольшим улучшением вашего алгоритма будет изменение цикла for на:

for (int i = 5; i < 100000; i = i + 2) {
    if (checkMod(i)) {
        primes.add(i);
    }
}

Это основано на предположении, что 1, 2 и 3 являются простыми числами, а все четные числа после этого не являются простыми числами. Это по крайней мере разрезает ваш алгоритм пополам.

Нет, это почти не влияет. Поиск композитов не простыми является дешевой частью пробного деления. Дорогая часть это проверка простых чисел. Ах, и1 is not a prime.
19

что вы делите только на простые числа.

private static boolean checkMod( int num) {
    for (int i : primes){
        if( num % i == 0){
            return false;
        }
    }
    return true;
}

Плохо то, что вы делите наall найденные простые числа, то есть все простые числа меньше, чем у кандидата. Это означает, что для наибольшего простого числа меньше одного миллиона, 999983, вы делите на 78497 простых чисел, чтобы узнать, что это число является простым числом. Это большая работа. Фактически, настолько много, что работа, потраченная на простые числа в этом алгоритме, составляет около 99,9% всей работы при переходе к миллиону, большую часть - для более высоких пределов. И этот алгоритм почти квадратичный, чтобы найти простые числаn таким образом, вы должны выполнить около

n² / (2*(log n)²)

подразделения.

Простое улучшение - остановить разделение раньше. Позволятьn составное число (то есть число, большее 1, с делителями, отличными от 1, иn), и разрешиd быть делителемn.

Сейчас,d быть делителемn Значит этоn/d является целым числом, а также делителемn: n/(n/d) = d. So we can naturally group the divisors of n на пары, каждый делительd рождает пару(d, n/d).

Для такой пары есть две возможности:

d = n/d, which means n = d², or d = √n. The two are different, then one of them is smaller than the other, say d < n/d. But that immediately translates to d² < n or d < √n.

Так или иначе, каждая пара делителей содержит (по крайней мере) один, не превышающий√nследовательно,if n is a composite number, its smallest divisor (other than 1) does not exceed √n.

Таким образом, мы можем остановить пробное разделение, когда мы достигнем√n:

private static boolean checkMod( int num) {
    for (int i : primes){
        if (i*i > n){
            // We have not found a divisor less than √n, so it's a prime
            return true;
        }
        if( num % i == 0){
            return false;
        }
    }
    return true;
}

Примечание: это зависит от списка простых чисел, которые повторяются в порядке возрастания. Если это не гарантировано языком, вы должны использовать другой метод, итерировать по индексу черезArrayList или что-то типа того.

Остановив пробное деление в квадратном корне кандидата для наибольшего простого числа меньше одного миллиона, 999983, теперь нам нужно только разделить его на 168 простых чисел ниже 1000. Это намного меньше работы, чем ранее. Прекращение пробного деления в квадратном корне и деление только на простые числа настолько же хорошо, насколько это возможно для пробного деления, и требует

2*n^1.5 / (3*(log n)²)

подразделения, дляn = 1000000это фактор около 750, неплохо, не так ли?

Но это все еще не очень эффективный, самый эффективный способ найти все простые числа нижеn сита Простой в реализации является классическимСито Эратосфена, Это находит простые числа нижеn в операциях O (n * log log n), с некоторыми улучшениями (исключающими из рассмотрения несколько кратных простых чисел), его сложность может быть уменьшена до операций O (n). Относительно новым ситом с лучшим асимптотическим поведением являетсяСито Аткина, который находит простые числаn в операциях O (n) или с улучшением исключения кратных чисел некоторых простых чисел в операциях O (n / log log n). Сито Аткина является более сложным для реализации, поэтому вероятно, что хорошая реализация сита Эратосфена работает лучше, чем наивная реализация сита Аткина. Для реализаций одинаковых уровней оптимизации разница в производительности мала, если ограничение не становится большим (больше 1010; и весьма распространено, что на практике сито эратосфена масштабируется лучше, чем сито аткина, из-за лучших схем доступа к памяти). Поэтому я бы рекомендовал начать с сита Эратосфена и только тогда, когда его производительность не удовлетворительная, несмотря на честные усилия по оптимизации, углубиться в сито Аткина. Или, если вы не хотите реализовывать это самостоятельно, найдите хорошую реализацию, которую кто-то уже серьезно настроил.

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

(3/4)*(1000000^0.5) = 750. :)
Спасибо Дэниел .. это так хорошо объяснено. dharam
@WillNess Aw, дерьмо, я должен действительно потратить время, чтобы написать это на бумаге. Благодарю.
0

предложенную Бенджамином Оманом выше, Это только одна модификация, чтобы избежать проверки на простоту всех чисел, заканчивающихся цифрой '5', поскольку эти числа, конечно, не являются простыми числами, так как они делятся на 5.

for (int i = 7;(i < 100000) && (!i%5==0); i = i + 2) {
    if (checkMod(i)) {
        primes.add(i);
    }
}

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

Итак, перед этим циклом, как этоprimes инициализируется? Содержит ли он какие-либо числа, такие как 2, 3 и 5?

Похожие вопросы