Эффективный алгоритм для получения простых чисел между двумя большими числами

Ответ 1

Я помню решение этой проблемы:

• Используйте сито eratosthenes, чтобы сгенерировать все простые числа ниже sqrt(1000000000) = ~32 000 в массиве primes.
• Для каждого номера x между m и n проверяется только если он выполняется путем тестирования делимости на числа <= sqrt(x) из массива primes. Таким образом, для x = 29 вы будете проверять только если он делится на 2, 3 and 5.

Нет смысла проверять делимость на простые числа, так как если x divisible by non-prime y, то существует такое простое число p < y, что x divisible by p, так как мы можем написать y как произведение простых чисел. Например, 12 делится на 6, но 6 = 2 * 3, что означает, что 12 также делится на 2 или 3. Генерируя все необходимые простые числа заранее (их очень мало), вы значительно сокращаете время, необходимое для фактического тестирования примитивов.

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

Вы можете сделать это быстрее, обобщая сито для генерации простых чисел в интервале [left, right], а не [2, right], как это обычно представлено в учебниках и учебниках. Однако это может стать довольно уродливым, и это не нужно. Но если кто-то заинтересован, см.:

http://pastie.org/9199654 и этот связанный ответ.

Ответ 2

Вы делаете много дополнительных разделов, которые не нужны - если вы знаете, что число не делится на 3, нет смысла проверять, делится ли оно на 9, 27 и т.д. Вы должны попытаться разделить только по потенциальным простым множителям числа. Кэшируйте набор простых чисел, которые вы генерируете, и проверяйте деление на предыдущие простые числа. Обратите внимание, что вам нужно сгенерировать начальный набор простых чисел ниже L1.

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

Вы также можете увеличивать на 2, чтобы вы могли игнорировать проверку, если четное число является простым (специальный корпус, номер 2, конечно.)

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

Ответ 3

Вы можете попробовать Сито Эратосфена. Основное отличие состоит в том, что вы начинаете с L1 вместо того, чтобы начинать с 2.

Ответ 4

Существует множество алгоритмов нахождения простых чисел. Некоторые быстрее, другие легче.

Вы можете начать с нескольких простых оптимизаций. Например,

• почему вы ищете, если каждое число является простым? Другими словами, вы уверены, что, учитывая диапазон от 411 до 418, необходимо искать, если числа 412, 414, 416 и 418 являются первичными? Номера, делящиеся на 2 и 3, могут быть пропущены с очень простыми модификациями кода.

• , если число не равно 5, но заканчивается цифрой "5" (1405, 335), это не простая плохая идея: это сделает поиск медленнее.

• как насчет кеширования результатов? Затем вы можете разделить на простые числа, а не на каждое число. Кроме того, речь идет только о простых числах меньше квадратного корня из числа, которое вы ищете.

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

Ответ 5

Немного изменим вопрос: как быстро вы можете генерировать простые числа между m и n и просто записывать их в память? (Или, возможно, на RAM-диск.) С другой стороны, помните диапазон параметров, как описано на странице проблемы: m и n могут достигать миллиарда, а нм - не более миллиона.

IVlad и Brian большинство конкурентного решения, даже если это правда, что более медленное решение может быть достаточно хорошим. Сначала генерировать или даже предкоммутировать простые числа меньше, чем sqrt (млрд.); их не так много. Затем сделайте усеченное сито из Eratosthenes: создайте массив длины n-m + 1, чтобы отслеживать состояние каждого числа в диапазоне [m, n], причем первоначально каждое такое число помечено как prime (1). Затем для каждого предварительно вычисленного простого p выполните цикл, который выглядит следующим образом:

for(k=ceil(m/p)*p; k <= n; k += p) status[k-m] = 0;

Этот цикл отмечает все числа в диапазоне m <= x <= n как составные (0), если они кратно p. Если это то, что Ивлад подразумевал под "довольно уродливым", я не согласен; Я не думаю, что это так плохо.

Фактически, почти 40% этой работы предназначено только для простых чисел 2, 3 и 5. Существует хитрость для объединения сита для нескольких простых чисел с инициализацией массива состояний. А именно, шаблон делимости на 2, 3 и 5 повторяет mod 30. Вместо инициализации массива для всех 1s вы можете инициализировать его повторяющимся шаблоном 010000010001010001010001000001. Если вы хотите быть еще более острым, вы можете продвинуться вперед k на 30 * p вместо p, и только отмечать кратные в одном шаблоне.

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

Ответ 6

Одна вещь, о которой никто не упоминал, заключается в том, что она довольно быстро для проверки единственного числа для простоты. Таким образом, если задействованный диапазон мал, но цифры большие (например, генерируют все простые числа от 1 000 000 000 до 1000 100 000), было бы быстрее просто проверить каждый номер для примитивности в отдельности.

Ответ 7

int ceilingNumber = 1000000;
int myPrimes = 0;


BitArray myNumbers = new BitArray(ceilingNumber, true);

for(int x = 2; x < ceilingNumber; x++)
    if(myNumbers[x])
    {
        for(int y = x * 2; y < ceilingNumber; y += x)
            myNumbers[y] = false;
    }


for(int x = 2; x < ceilingNumber; x++)
    if(myNumbers[x])
    {
        myPrimes++;
        Console.Out.WriteLine(x);

    }

Console.Out.WriteLine("======================================================");

Console.Out.WriteLine("There is/are {0} primes between 0 and {1} ",myPrimes,ceilingNumber);

Console.In.ReadLine();

Ответ 8

import java.io.*;
import java.util.Scanner;
class Test{
public static void main(String args[]){

   Test tt=new Test();
   Scanner obj=new Scanner(System.in);
   int m,n;
      System.out.println(i);
   m=obj.nextInt();
   n=obj.nextInt();
   tt.IsPrime(n,m);
     }
   public void IsPrime(int num,int k)
   {
       boolean[] isPrime = new boolean[num+1];
       // initially assume all integers are prime
        for (int i = 2; i <= num; i++) {
            isPrime[i] = true;
        }

        // mark non-primes <= N using Sieve of Eratosthenes
        for (int i = 2; i*i <= num; i++) {

            // if i is prime, then mark multiples of i as nonprime
            // suffices to consider mutiples i, i+1, ..., N/i
            if (isPrime[i]) {
                for (int j = i; i*j <=num; j++) {
                    isPrime[i*j] = false;
                }
            }
        } 
        for (int i =k; i <= num; i++) {
            if (isPrime[i]) 
            {
                     System.out.println(i);
            }
        }

    }

}

Ответ 9

Я думаю, что у меня очень быстрый и эффективный алгоритм генерации всего простого, даже если вы используете алгоритм BigInteger, чтобы получить простое число, это намного быстрее и проще, чем любой другой, и я использую его для решения почти проблемы, связанной с простым числом в Project Euler всего за несколько секунд для полного решения (грубая сила)  Вот код Java:

public boolean checkprime(int value){  //Using for loop if need to generate prime in a 
    int n, limit;                        
    boolean isprime;

    isprime = true;
    limit = value / 2;
    if(value == 1) isprime =false;

    /*if(value >100)limit = value/10;  // if 1 number is not prime it will generate
    if(value >10000)limit = value/100; //at lest 2 factor (not 1 or itself)
    if(value >90000)limit = value/300; // 1 greater than  average 1  lower than average
    if(value >1000000)limit = value/1000; //ex: 9997 =13*769 (average ~ sqrt(9997) is 100)
    if(value >4000000)limit = value/2000; //so we just want to check divisor up to 100
    if(value >9000000)limit = value/3000; // for prime ~10000 
    */

    limit = (int)Math.sqrt(value); //General case
    for(n=2; n <= limit; n++){
        if(value % n == 0 && value != 2){
            isprime = false;
            break;
        }
    }
    return isprime;
}

Ответ 10

List<int> prime(int x, int y)
    {
        List<int> a = new List<int>();
        int b = 0;
        for (int m = x; m < y; m++)
        {
            for (int i = 2; i <= m / 2; i++)
            {
                b = 0;
                if (m % i == 0)
                {
                    b = 1;
                    break;
                }
            }
            if (b == 0) a.Add(m)`
        }
      return a;
   }