Ich habe mich seit Jahren für das Problem interessiert, einen besseren Primzahlerkenner zu finden. Mir ist klar, dass dies ein riesiges Gebiet der akademischen Forschung und des Studiums ist - mein Interesse daran ist wirklich nur zum Spaß. Hier war mein erster Versuch einer möglichen Lösung in C (unten).

Meine Frage ist, können Sie eine Verbesserung vorschlagen (ohne einen anderen Verweis im Netz zu zitieren, suche ich nach aktuellem C-Code)? Ich versuche, daraus ein besseres Verständnis für die Ermittlung der Leistungskomplexität einer solchen Lösung zu gewinnen.

Bin ich richtig in der Schlussfolgerung, dass die Komplexität dieser Lösung O (n ^ 2) ist?

#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;
}