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

Question

Недавно я участвовал в небольшом конкурсе Java-программирования в моей школе. Мой партнер и я только что закончили наш первый чистый класс oop, и большинство вопросов были вне нашей лиги, поэтому мы остановились на этом (и я немного перефразирую): обратная сторона также проста, например, если n = 18, ваша программа должна вывести 31 ", потому что 31 и 13 являются простыми. В вашем файле .class будет передан контрольный пример всех возможных чисел от 1 до 2 000 000 000, и он должен будет вернуть правильный ответ в течение 10 секунд, чтобы его считали действительным.

Мы нашли решение, но для более крупных тестовых случаев это заняло бы больше 10 секунд. Я вполне уверен, что есть способ сдвинуть диапазон циклов с n, .. 2 000 000 000, так как вероятная капля необходимости зацикливаться так далеко, когда n - небольшое число, мала, но в любом случае мы прервали цикл, когда число прост при обоих условиях найден. Сначала мы выполняли цикл от 2, .. n независимо от того, насколько велик он был, потом я вспомнил правило о циклическом переходе только к квадратному корню из n. Любые предложения о том, как сделать мою программу более эффективной? У меня не было классов, занимающихся анализом сложности алгоритмов. Вот наша попытка.

public class P3
{

   public static void main(String[] args){

    long loop = 2000000000;
    long n = Integer.parseInt(args[0]);
    for(long i = n; i<loop; i++)
    {
      String s = i +"";
      String r = "";
      for(int j = s.length()-1; j>=0; j--)
        r = r + s.charAt(j);
      if(prime(i) && prime(Long.parseLong(r)))
      {
          System.out.println(i);
          break;
      }
    }
    System.out.println("#");
  }

  public static boolean prime(long p){


for(int i = 2; i<(int)Math.sqrt(p); i++)
    {
      if(p%i==0)
        return false;
    }
    return true;
  }
}

ps извините, если я сделал неправильное форматирование кода, это мой первый пост здесь. Кроме того, в выходных данных должен был стоять знак «#» после каждой строки, о чем говорит строка после цикла Спасибо за любую помощь, которую вы, ребята, предлагаете !!!

Answer 1

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

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

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

Answer 2

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

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

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

Edit:

Вот пример, который я быстро собрал в 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 в источнике результат отображается мгновенно.

Answer 3

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

Answer 4

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

Answer 5

@ Дэвид получает квадратный корень из числа, а затем зацикливается, пока квадратный корень не устранит четные числа и не выяснит, не делится ли он на

Answer 6

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

Если вы пишете свою собственную реализацию (например, для назначения), я бы порекомендовал работать с алгоритмом псевдокода в книге, чтобы вы понимали, что делаете.

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

typedef uint64_t BigIntT;
typedef int64_t SBigIntT;

// This function calculations the power of b^e mod phi
// As long as 
//      b*b is smaller than max(BigIntT) 
//      b*phi is smaller than max(BigIntT)
// we will not have overflow.
BigIntT calculatePower (BigIntT b, BigIntT e, BigIntT m) {
    BigIntT result = 1;

    while (e != 0) {
        if (e & 1) {
            result = (result * b) % m;
        }

        e = e >> 1;
        b = (b * b) % m;
    }

    return result;
}

// This function implements simple jacobi test.
// We can expect compiler to perform tail-call optimisation.
SBigIntT jacobi (SBigIntT a, SBigIntT b) {
    if (a == 0 || a == 1) {
        return a;
    } else if (a % 2 == 0) {
        if (((b*b - 1) / 8) % 2 == 0) {
            return jacobi(a/2, b);
        } else {
            return -jacobi(a/2, b);
        }
    } else if ((((a-1) * (b-1)) / 4) % 2 == 0) {
        return jacobi(b % a, a);
    } else {
        return -jacobi(b % a, a);
    }
}

// This function implements : http://en.wikipedia.org/wiki/Solovay-Strassen_primality_test
bool testPrime (BigIntT p) {
    int tests = 10;

    if (p == 2) {
        return true;
    }

    while (tests-- > 0) {
        BigIntT a = generateRandomNumber(2, p);

        if (greatestCommonDivisor(a, p) == 1) {
            BigIntT l = calculatePower(a, (p-1)/2, p);
            SBigIntT j = jacobi(a, p);

            // j % p == l
            if ((j == -1) && (l == p-1) || (j == l)) {
                // So far so good...
            } else {
                // p is composite
                return false;
            }
        } else {
            // p is composite
            return false;
        }
    }

    return true;
}

Производительность очень хорошая, даже с большими числами.

Answer 7

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

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

Answer 8

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

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

Answer 9

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

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

Answer 10

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

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

если число оканчивается на 0,2,4,5,6 или 8, оно не простое / кроме 2-х

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

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

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