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

Question

Я новичок в C #, я пытаюсь написать приложение, чтобы получить простые числа между двумя числами, введенными пользователем. Проблема в том, что при больших числах (допустимые числа находятся в диапазоне от 1 до 1000000000) получение простых чисел занимает много времени, и в соответствии с решаемой мной проблемой вся операция должна выполняться за небольшой промежуток времени. Это ссылка на проблему для более подробного объяснения: SPOJ-Prime

А вот часть моего кода, которая отвечает за получение простых чисел:

  public void GetPrime()
    {            
        int L1 = int.Parse(Limits[0]);
        int L2 = int.Parse(Limits[1]);

        if (L1 == 1)
        {
            L1++;
        }

        for (int i = L1; i <= L2; i++)
        {
            for (int k = L1; k <= L2; k++)
            {
                if (i == k)
                {
                    continue;
                }
                else if (i % k == 0)
                {
                    flag = false;
                    break;
                }
                else
                {
                    flag = true;
                }
            }

            if (flag)
            {
                Console.WriteLine(i);
            }
        }
    }

Есть ли более быстрый алгоритм? Заранее спасибо.

Answer 1

Я помню, как решал проблему следующим образом:

1. Используйте сито с эратосфенами для генерации всех простых чисел ниже sqrt(1000000000) = ~32 000 в массиве primes.
2. Для каждого числа 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 и этот связанный ответ .

Answer 2

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

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

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

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

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

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

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

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

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

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

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

Answer 7

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

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

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

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

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

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

Answer 8

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

Answer 9

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

    }

}

Answer 10

Я думаю, что у меня есть очень быстрый и эффективный (генерирующий все простые числа, даже если используется тип 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;
}