Optimierung mit Codierung

Question

Ich habe ein Programm für Primzahlen, aber ich muss es optimieren. Irgendwelche Hinweise?

int num, i, count = 0; 

    printf("Type a non-negative integer:\n"); 

scanf("%d", &num); 

    if((num%2 == 0)&& (num != 2)||(num == 1)){ 

    printf("%d is not a prime number.\n", num); 

    } else if(num == 2){ 

    printf("%d is a prime number.\n", num); 

    } else { 

    for(i = 3; i < num; i += 2){ 

     if(num%i == 0){ 

    count++; 

    break; 

     } 

    } 

    if(count == 0){ 

     printf("%d is a prime number.\n", num); 

    } else { 

     printf("%d is not a prime number.\n", num); 

    } 

    } 

} 

Answer 1

Sie müssen nur bis zur Quadratwurzel von num überprüfen. Weitere Hinweise finden Sie unter testing primes.

Answer 2

Ich denke, das ist eines der grundlegenden Probleme, die Sie selbst lösen könnten! Ich kann Ihnen helfen, dieses Problem zu lösen; Beginnen Sie mit einem Blick auf die Definition der Primzahlen:

Eine Primzahl ist eine Zahl, die nur durch 1 und sich selbst dividiert werden kann. Angenommen, wir nennen es N dann N ist nur durch 1 und N teilbar, und die Nummer 1 ist nicht prim.

Die Idee ist:

1 - wenn die Nummer 1 ist nicht prim!

2 - wenn Nummer 2 ist eine Primzahl

3 - sonst ----> wir initialisieren i = 2, dann starten Sie den Wert von N% Berechnung i; wenn es 0 ist, ist die Zahl nicht prim, sonst müssen wir i erhöht um 1.

Wir tun Schritt 3 bis i < N (oder i < = sqrt (N))

Wenn die Nummer ist nicht teilbar von i, dann ist es Prime!

Hier ist eine einfache Implementierung:

int n ; 
printf("enter n:"); 
scanf("%d",&n); 
if(n<=1) printf("is not prime"); 
else if(n==2) printf("is prime"); 
else{ 
    bool flag = true; 
    for(int i = 2 ; i < n ; i++) 
     if(n%i==0){ 
     flag = false; 
     break; 
     } 
    if(flag) printf("is prime"); 
    else printf("is not prime"); 
} 

Es gibt einen besseren Algorithmus eine Reihe von Primzahlen zu finden; Ich denke, es ist besser, es zu lernen:

Sieve of Eratosthenes

Ich hoffe, das Tutorial, um herauszufinden, hilft, was eine Primzahl ist.