Estou interessado no problema de encontrar um melhor reconhecedor de números primos há anos. Sei que essa é uma área enorme de pesquisa e estudo acadêmico - meu interesse é realmente apenas por diversão. Aqui foi minha primeira tentativa de uma possível solução, em C (abaixo).

Minha pergunta é: você pode sugerir uma melhoria (sem citar alguma outra referência na rede, eu estou procurando pelo código C real)? O que estou tentando obter disso é uma melhor compreensão da determinação da complexidade de desempenho de uma solução como essa.

Estou certo ao concluir que a complexidade desta solução é 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;
}