Wie kann ich dieses sehr kleine C-Programm schneller machen?

Question

Gibt es eine einfache Möglichkeit, dieses kleine Programm schneller zu machen? Ich habe es für eine Aufgabe gemacht, und es ist korrekt, aber zu langsam. Das Ziel des Programms ist es, das n-te Paar Primzahlen zu drucken, wobei der Unterschied zwischen den beiden zwei ist, wobei n gegeben ist.

#include <stdio.h> 
#include <stdlib.h> 
#include <stdbool.h> 

bool isPrime(int number) { 
    for (int i = 3; i <= number/2; i += 2) { 
    if (!(number%i)) { 
     return 0; 
    } 
    } 

    return 1; 
} 

int findNumber(int n) { 
    int prevPrime, currentNumber = 3; 

    for (int i = 0; i < n; i++) { 
    do { 
     prevPrime = currentNumber; 

     do {        
     currentNumber+=2; 
     } while (!isPrime(currentNumber)); 

    } while (!(currentNumber - 2 == prevPrime)); 
    } 

    return currentNumber; 
} 

int main(int argc, char *argv[]) { 
    int numberin, numberout; 
    scanf ("%d", &numberin); 

    numberout = findNumber(numberin); 

    printf("%d %d\n", numberout - 2, numberout); 
    return 0; 
} 

ich als eine Art von Array oder eine Liste verwenden, die alle Primzahlen bis die aktuelle Nummer gefunden und teilen jede Nummer durch diese Liste anstelle aller Zahlen enthalten würde, aber wir haben nicht wirklich diese unterschiedlichen Datenstrukturen bedeckt Trotzdem denke ich, dass ich in der Lage sein sollte, dieses Problem ohne zu lösen. Ich fange gerade mit C an, aber ich habe etwas Erfahrung in Python und in Java.

Answer 1

Hier ist eine Verbesserung der Schleife in isPrime zu beschleunigen:

bool isPrime(int number) { 
    for (int i = 3; i * i <= number; i += 2) { // Changed the loop condition 
    if (!(number%i)) { 
     return 0; 
    } 
    } 

    return 1; 
} 

Answer 2

Du isPrime öfter als nötig aufrufen. Sie schrieb

currentNummber = 3; 
/* ... */ 
do {        
    currentNumber+=2; 
} while (!isPrime(currentNumber)); 

... was bedeutet, dass isPrime für jede ungerade Zahl genannt wird. Wenn Sie jedoch festgestellt haben, dass z.B. 5 ist prime, Sie können bereits sagen, dass 10, 15, 20 usw. nicht prim sind, also müssen Sie sie nicht testen.

Dieser Ansatz des "Durchstreichens" von Vielfachen von Primzahlen wird durchgeführt, wenn ein Siebfilter verwendet wird, siehe z.B. Sieve of Eratosthenes algorithm in C für eine Implementierung eines Siebfilters für Primzahlen in C.

Answer 3

Um Paare von Primzahlen zu finden, die sich durch 2 unterscheiden, müssen Sie nur eine Primzahl finden und dann 2 hinzufügen und testen, ob es auch Primzahl ist.

if (isPrime(x) && isPrime(x+2)) { /* found pair */ } 

Primzahlen den besten Algorithmus zu finden, ist die Sieve of Eratosthenes. Sie müssen eine Nachschlagetabelle bis zu (N) erstellen, wobei N die maximale Anzahl ist, die Sie erhalten können. Sie können das Sieb verwenden, um in O (1) zu gelangen, wenn eine Zahl prim ist. Beim Erstellen des Sieve können Sie eine Liste sortierter Primzahlen erstellen.

Wenn Ihr N groß ist, können Sie auch davon profitieren, dass eine Zahl P prim ist, wenn sie keine Primfaktoren hat < = SQRT (P) (denn wenn sie einen Faktor> SQRT (N) hat) es sollte auch eine < SQRT (N)) haben. Sie können ein Sieb von Eratosthenes mit der Größe SQRT (N) erstellen, um eine Liste von Primzahlen zu erhalten, und dann testen, ob eine dieser Primzahlen P trennt. Wenn keine P trennt, ist P Primzahl.

Mit diesem Ansatz können Sie Zahlen bis zu 1 Milliarde oder mehr relativ schnell und mit wenig Speicher testen.

Answer 4

Vermeiden Test jemals 3. Kandidat

Paare von Primzahlen a, a+2 nur a = 6*n + 5 gefunden werden kann. (außer Paar 3,5).

Warum?

a + 0 = 6*n + 5 Maybe a prime 
a + 2 = 6*n + 7 Maybe a prime 
a + 4 = 6*n + 9 Not a prime when more than 3 as 6*n + 9 is a multiple of 3 

Also anstatt Test jemals andere ganze Zahl mit + 2, Test mit

a = 5; 
loop { 
    if (isPrime(a) && isPrime(a+2)) PairCount++; 
    a += 6; 
} 

---

Schleife Ausgang Test verbessern

Viele Prozessoren/Compiler, wenn der Rest der Berechnung wird Außerdem steht für nahezu "freie" CPU-Zeitkosten der Quotient zur Verfügung. YMMV. Verwenden Sie den Quotienten statt i <= number/2 oder i*i <= number, um die Testschleife zu begrenzen.

Die Verwendung von sqrt() hat eine Reihe von Problemen: Bereich von double vs int, Genauigkeit, Umwandlung in/aus Integer. Empfehlen Sie sqrt() für diese Aufgabe zu vermeiden.

Verwenden Sie unsigned für zusätzlichen Bereich.

bool isPrime(unsigned x) { 
    // With OP's selective use, the following line is not needed. 
    // Yet needed for a general purpose `isPrime()` 
    if (x%2 == 0) return x == 2; 

    if (x <= 3) return x == 3; 
    unsigned p = 1; 
    unsigned quotient, remainder; 
    do { 
    p += 2; 
    remainder = x%p; 
    if (remainder == 0) return false; 
    quotient = x/p;   // quotient for "free" 
    } while (p < quotient); // Low cost compare 
    return true; 
}