Ты простое число

Question

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

Мой вопрос: можете ли вы предложить улучшение (не ссылаясь на какую-то другую ссылку в сети, я ищу реальный код C)? Из этого я пытаюсь лучше понять сложность производительности решения, подобного этому.

Прав ли я, заключая, что сложность этого решения составляет O (n ^ 2)?

#include <stdio.h>
#include <math.h>

/* isprime                                                           */
/* Test if each number in the list from stdin is prime.              */
/* Output will only print the prime numbers in the list.             */

int main(int argc, char* argv[]) {

    int returnValue = 0;
    int i;
    int ceiling;
    int input = 0;
    int factorFound = 0;

    while (scanf("%d", &input) != EOF) {

        ceiling = (int)sqrt(input);
        if (input == 1) {
            factorFound = 1;
        }

        for (i = 2; i <= ceiling; i++) {
            if (input % i == 0) {
                factorFound = 1;
            } 
        }

        if (factorFound == 0) {
            printf("%d\n", input);
        }

        factorFound = 0;    
    } 

    return returnValue;
}

Answer 1

   for (i = 2; i <= ceiling; i++) {
        if (input % i == 0) {
            factorFound = 1;
            break;
        } 
    }

Это первое улучшение, которое сделано и остается в рамках «того же» алгоритма.Для этого не требуется никакой математики.

Кроме того, как только вы увидите, что input не делится на 2, нет необходимости проверять 4, 6, 8 и т. Д.Если любое четное число делится на input, то, безусловно, будет 2, потому что оно делит все четные числа.

Если вы хотите немного выйти за пределы алгоритма, вы можете использовать цикл, подобныйчто Шелдон Л. Купер дает в своем ответе.(Это просто легче, чем заставить его исправить мой код из комментариев, хотя его усилия высоко ценятся)

это использует тот факт, что каждое простое число, кроме 2 и 3, имеет форму n*6 + 1 или n*6 - 1 для некоторого положительного целого числа n.Чтобы увидеть это, просто обратите внимание, что если m = n*6 + 2 или m = n*6 + 4, то n делится на 2. Если m = n*6 + 3, то он делится на 3.

На самом деле, мы можем принять это далее,Если p1, p2, .., pk являются первыми k простыми числами, то все целые числа, взаимно простые с их произведением, отмечают «слоты», в которые должны вписаться все остальные простые числа.

, чтобы увидеть это, просто позвольте k# быть произведением всех простых чисел до pk.тогда, если gcd(k#, m) = g, g делит n*k# + m, и, таким образом, эта сумма тривиально сложна, если g != 1.так что если вы хотите выполнить итерацию в терминах 5# = 30, то ваши простые целые числа равны 1, 7, 11, 13, 17, 19, 23 и 29.

---

технически, я не доказалмоя последняя претензияЭто не намного сложнее

, если g = gcd(k#, m), то для любого целого числа n, g делит n*k# + m, потому что оно делит k#, поэтому оно также должно делить n*k#.Но он также делит m, поэтому он должен делить сумму.Выше я только доказал это для n = 1.мой плохой.

---

Кроме того, я должен отметить, что ничто из этого не меняет фундаментальную сложность алгоритма, это все равно будет O (n ^ 1/2).Все, что он делает, это радикально , уменьшая коэффициент, который используется для расчета фактического ожидаемого времени выполнения.

Answer 2

Сложность времени для каждого теста простоты в вашем алгоритме равна O(sqrt(n)).

Вы всегда можете использовать тот факт, что все простые числа, кроме 2 и 3, имеют вид: 6*k+1 или 6*k-1.Например:

int is_prime(int n) {
  if (n <= 1) return 0;
  if (n == 2 || n == 3) return 1;
  if (n % 2 == 0 || n % 3 == 0) return 0;
  int k;
  for (k = 6; (k-1)*(k-1) <= n; k += 6) {
    if (n % (k-1) == 0 || n % (k+1) == 0) return 0;
  }
  return 1;
}

Эта оптимизация не улучшает асимптотическую сложность.

РЕДАКТИРОВАТЬ

Учитывая, что в вашем коде вы неоднократно проверяете числаВы можете предварительно рассчитать список простых чисел.Существует только 4792 простых числа, которые меньше или равны квадратному корню из INT_MAX (при условии 32-битных целых).

Кроме того, если входные числа относительно невелики, вы можете попробовать вычислить сито .

Вот комбинация обеих идей:

#define UPPER_BOUND 46340  /* floor(sqrt(INT_MAX)) */
#define PRIME_COUNT 4792  /* number of primes <= UPPER_BOUND */

int prime[PRIME_COUNT];
int is_prime_aux[UPPER_BOUND];

void fill_primes() {
  int p, m, c = 0;
  for (p = 2; p < UPPER_BOUND; p++)
    is_prime_aux[p] = 1;
  for (p = 2; p < UPPER_BOUND; p++) {
    if (is_prime_aux[p]) {
      prime[c++] = p;
      for (m = p*p; m < UPPER_BOUND; m += p)
        is_prime_aux[m] = 0;
    }
  }
}

int is_prime(int n) {
  if (n <= 1) return 0;
  if (n < UPPER_BOUND) return is_prime_aux[n];
  int i;
  for (i = 0; i < PRIME_COUNT && prime[i]*prime[i] <= n; i++)
    if (n % prime[i] == 0)
      return 0;
  return 1;
}

Вызовите fill_primes в начале вашей программы перед началом обработки запросов.Работает довольно быстро.

Answer 3

Ваш код там имеет только сложность O (sqrt (n) lg (n)).Если вы предполагаете, что основными математическими операциями являются O (1) (истинно до тех пор, пока вы не начнете использовать bignums), то это просто O (sqrt (n)).

Обратите внимание, что тест на простоту можно выполнить быстрее чем O(sqrt (n) lg (n)) время. Этот сайт имеет ряд реализаций теста простоты AKS *1006*, который, как было доказано, работает за O ((log n) ^ 12) времени.

ТамЭто также очень и очень быстрые пробалистические тесты - хотя они и бывают быстрыми, они иногда дают неверный результат.Например, тест примитивности Ферма :

Учитывая число p, которое мы хотим проверить на простоту, выберите случайное число a и проверьте, является ли a^(p-1) mod p = 1,Если false, p определенно не простое число.Если это правда, p это , вероятно, простое число.Повторяя тест с разными случайными значениями a, вероятность ложноположительного результата можно уменьшить.

Обратите внимание, что у этого конкретного теста есть некоторые недостатки - подробности см. На странице Википедии,и другие вероятностные тесты простоты, которые вы можете использовать.

Если вы хотите придерживаться текущего подхода, есть ряд незначительных улучшений, которые все еще могут быть сделаны - как уже отмечали другие, после 2, вседальнейшие простые числа нечетны, поэтому вы можете пропустить два потенциальных фактора за раз в цикле.Вы также можете разразиться сразу же, когда вы найдете фактор.Однако это не меняет асимптотическое поведение вашего алгоритма в худшем случае, которое остается равным O (sqrt (n) lg (n)) - оно просто меняет лучший случай (на O (lg (n))), иуменьшает постоянный коэффициент примерно наполовину.

Answer 4

Можете ли вы предложить улучшение

Вот, пожалуйста ... не для алгоритма, а для самой программы:)

• Если вы не собираетесь использовать argc и argv, избавьтесь от них
• Что если я введу «сорока двух»? Сравните scanf () == 1, а не != EOF
• Не нужно приводить значение sqrt()
• returnValue не требуется, вы можете вернуть константу: return 0;
• Вместо того, чтобы использовать все функции внутри функции main(), разделите вашу программу на столько функций, сколько вы можете придумать.

Answer 5

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

   for (i = 2; i <= ceiling && !factorFound; i++) {
        if (input % i == 0) {
            factorFound = 1;

Другая возможность - увеличить счетчик на 2 (после проверки самой 2).*

Answer 6

#include <stdio.h>
#include <math.h>

int IsPrime (int n) {
  int i, sqrtN;
  if (n < 2) { return 0; } /* 1, 0, and negatives are nonprime */
  if (n == 2) { return 2; }
  if ((n % 2) == 0) { return 0; } /* Check for even numbers */
  sqrtN = sqrt((double)n)+1; /* We don't need to search all the way up to n */
  for (i = 3; i < sqrtN; i += 2) {
    if (n % i == 0) { return 0; } /* Stop, because we found a factor! */
  }
  return n;
}

int main()
{
  int n;
  printf("Enter a positive integer: ");
  scanf("%d",&n);
  if(IsPrime(n))
     printf("%d is a prime number.",n);
  else
     printf("%d is not a prime number.",n);
  return 0;
}

Answer 7

Вот мой алгоритм, Сложность остается O(n^0.5), но мне удалось удалить некоторые дорогие операции в коде ...

Самая медленная часть алгоритма - операция modulus, мне удалось устранить sqrt или выполнить i * i <= n

Таким образом, я сохраняю драгоценные циклы ... основываясь на том факте, что sum of odd numbers is always a perfect square.

Так как мы в любом случае перебираем odd numbers, почему бы не использовать его? :)

int isPrime(int n)
{
    int squares = 1;
    int odd = 3;

    if( ((n & 1) == 0) || (n < 9)) return (n == 2) || ((n > 1) && (n & 1));
    else
    {
        for( ;squares <= n; odd += 2)
        {
            if( n % odd == 0) 
                return 0;
            squares+=odd;
        }
        return 1;
    }
}

Answer 8

Временная сложность вашей программы O(n*m^0.5).С n количество простых чисел на входе.И m размер самого большого простого числа на входе, или MAX_INT, если вы предпочитаете.Таким образом, сложность также может быть записана как O(n) с n числом проверяемых простых чисел.

При Big-O n (обычно) является размером входного сигнала, в вашем случае это будетколичество простых чисел для проверки.Если бы я сделал этот список в два раза больше (например, дублируя его), это заняло бы (+ -) ровно в два раза больше, таким образом O(n).

Answer 9

Вы можете сделать небольшие сокращения в вашем алгоритме, не добавляя слишком много сложности кода.Например, вы можете пропустить четные числа в своем подтверждении и остановить поиск, как только найдете фактор.

if (input < 2 || (input != 2 && input % 2 == 0))
  factorFound = 1;

if (input > 3)
  for (i = 3; i <= ceiling && !factorFound; i += 2)
    if (input % i == 0)
      factorFound = 1;

Что касается сложности, если n - это ваш вводимый номер, то не будетсложность будет O (sqrt (n)), как вы делаете примерно максимум sqrt (n) делений и сравнений?

Answer 10

Четные числа (кроме 2) не могут быть простыми числами. Итак, когда мы знаем, что число не четное, мы можем просто проверить, являются ли нечетные числа его факторами.

for (i = 3; i <= ceiling; i += 2) {
        if (input % i == 0) {
            factorFound = 1;
            break;
        } 
    }