Are You A Prime Number

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