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

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

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

Кроме того, как только вы увидите, что input не делится на 2, нет необходимости проверять 4, 6, 8 и т. д. Если бы любое четное число делилось на input, то 2 обязательно делилось бы на 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). Все, что он делает, это значительно уменьшает коэффициент, который используется для расчета фактического ожидаемого времени выполнения.

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

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

Обратите внимание, что проверка простоты может быть выполнена быстрее, чем O(sqrt(n)lg(n)) за время. На этом сайте есть несколько реализаций тест на простоту AKS, который, как было доказано, работает за время 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))) и уменьшает постоянный коэффициент примерно вдвое.

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

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

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

Вы можете предложить улучшение

Вот так... не за алгоритм, а за саму программу :)

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

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

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) делений и сравнений?

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

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

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

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

Вот мой алгоритм, сложность остается 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;
    }
}

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

РЕДАКТИРОВАТЬ: Конечно, поскольку ему не нужно знать все факторы, просто является ли это простым числом. Отличное место.