Проверка, является ли интервал главным более эффективно

Сначала вы должны предварительно вычислить все простые числа до 2 000 000 000, используя что-то вроде Сито Эратосфена . Вы можете сохранить в битовом массиве, является ли каждое число простым.

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

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

Ваша проверка на простоту очень неэффективна. На самом деле, вам не нужно повторно проверять кратные уже проверенные числа. Поэтому, когда вы проверяете %2, вам не нужно проверять %4.

Чтобы узнать, является ли число простым, достаточно попытаться разделить его на все известные простые числа, пока не будет получен квадратный корень из проверяемого числа. Это значительно сокращает количество делений: если в вашем приложении есть список простых чисел от 2...~44721 (например, вычисленный в качестве подготовительного шага), вы можете довольно быстро проверить все числа до 2000000000.

Также следует убедиться, что сначала проверяется меньшее из двух перестановок (например, в вашем примере сначала проверяется 13, затем 31).

Редактировать:

Вот пример, который я быстро собрал на C# (чтобы запустить его на Java, вам придется внести небольшие синтаксические изменения, но у меня под рукой был компилятор C#):

public static long reverse(long value) {
    long result = 0;
    while (value > 0) {
        result = result*10+(value%10);
        value /= 10;
    }
    return result;
}

public static long[] knownPrimes = new long[1000000];
public static int knownPrimeCount = 0;

public static bool isPrime(long value) {
    // we loop through all already known primes and try to divide by those (sieve sort of)
    for (int primeIndex = 0; primeIndex < knownPrimeCount; primeIndex++) {
        long primeToCheck = knownPrimes[primeIndex];
        if (value % knownPrimes[primeIndex] == 0) {
            // can be divided by the given prime -> not a prime
            return false;
        }
        if ((primeToCheck * primeToCheck) > value) {
            // square exceeds the value -> is a prime, no more checks needed
            return true;
        }
    }
    // if we come here, we've run out of primes to check against, and therefore we should indicate this as error
    throw new ArgumentException(string.Format("{0} is too large to be checked against known primes", value), "value");
}

public static void Main(String[] args){
    long loop = 2000000000;
    long n =    1999990000;

    // first we initialize all the primes we may be needing for the final computation
    knownPrimes[knownPrimeCount++] = 2;
    for (long i = 3; true; i++) {
        if (isPrime(i)) {
            // store the new prime
            knownPrimes[knownPrimeCount++] = i;
            if ((i * i) > loop) {
                break; // we have all the primes we need now
            }
        }
    }

    // now we try to find matches
    for (long i = n; i <= loop; i++) {
        long reversed = reverse(i);
        if ((reversed <= i) && isPrime(reversed) && isPrime(i)) {
            Console.WriteLine("{0} <-> {1}", i, reversed);
        }
    }
    Console.WriteLine("#");
    Console.ReadKey(true);
}

На моем компьютере и с заданными loop и n в исходнике результат появляется мгновенно.

Использование BigInteger.isProbablePrime (уверенность) и BigInteger.nextProbablePrime () может значительно сократить количество случаев, которые необходимо проверять достаточно эффективно

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

Я не делал этого раньше, но вот некоторые вещи, которые приходят мне на ум.

Если ваш квадратный корень - целое число, то число не простое

Если число заканчивается на 0, 2, 4, 5, 6 или 8, то оно не простое, за исключением 2

Число можно разделить на 3, если сумма цифр делится на 3. и на 9, если сумма равна 9.

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

О, и, конечно, ваша эффективность значительно возрастет, если вы сделаете что-то вроде Miller-Rabin primality test http://en.wikipedia.org/wiki/Miller-Rabin_primality_test. Ваш фактический тест нужно проводить только в тех случаях, которые не являются определенными.

Еще одно улучшение скорости, которое вы можете сделать в main , - это изменить свой цикл для предварительной фильтрации некоторых составных чисел, развернув некоторые итерации в последовательность тестов. Самый простой - проверить 2 вне цикла, а затем проверить нечетные числа ( 2 * i + 1 ). Немного сложнее проверить 2, 3, затем 6 * i ± 1 . Вы можете продолжать расширять этот подход, тестируя первые n простых чисел, а затем зацикливая печь p n # * i + j , где p _n # - это простое первичное (произведение первых n простых чисел), а j - положительное целое число, меньшее чем и взаимно простое с p _n #.

Чтобы ускорить метод простое , вы можете начать с быстрого вероятностного простого теста и протестировать с использованием более медленного детерминированного теста только для тех случаев, которые вероятностный тест не может определить.

Похоже, вы увеличиваете на 1, но вы должны увеличивать на 2. Никакое четное число не является простым, кроме 2.

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

@Graham... также здорово, что я прочитал статью о тесте, который вы упомянули, потому что, хотя я думаю, что понял суть из ваших комментариев, Python всегда выглядит для меня как греческий язык. Я знаю, что все говорят, что это один из самых простых языков, но по какой-то причине java и c++ всегда выглядят для меня более читабельными. В любом случае, да, это был бы лучший способ сделать это. Еще раз спасибо всем, кто давал мне советы, я многому научился на этом форуме. Не могу дождаться моего класса по структурам данных и алгоритмам осенью!!!

Еще быстрее, чем все это, используется тест Миллера-Рабина . Это вероятностный тест и, следовательно, имеет определенный уровень погрешности; однако тест запускается несколько раз, что позволяет уменьшить эту ошибку до минимума (50 часто бывает достаточно для коммерческих приложений).

Не на Java, но вот быстрая реализация на Python, которую я придумал.