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