Hallo Leute. Berechnung von Primzahlen geht bei einzelen Prinzahlen schneller ohne das Sieb.
Das Sieb prüft kurz gesagt alle Zahlen, indem es alle Zahlen in einem geählten bereich z.B. 1-10.000 durch 2 teilt, alle die teilbar waren raus schmeißt, und dann mit der nächsten übrig gebliebenen Zahl, also 3, dann 5 etc, weiter macht.
Vorteil: 1) Alle Primzahlen im Bereich 2) Auf dem Papier machbar
Nachteil: rechenintensiv.
Wolltest du also das Sieb probieren.... Wolltest du aber nur eine Zahl auf "primhaftigkeit" prüfen geht das viel schneller. Einfach hochzählen von 2 (n) ab. Damit teilen. Dann innerhalb einer Schleife einfach immer prüfen, ob sich n ohne Rest teilen lässt. Wenn ja, keine Primzahl. Wenn nein einen hoch zählen und weiter (also mit n+1). Und wieder prüfen ob ihne Rest teilbar. So kommst du zu dem Punkt, wo sich eine Zahl durch n ohne Rest teilen lässt. Dann prüfst du noch ob n == Zahl. Wenn ja dann Primzahl. wenn nein (n ist dann automatisch kleiner als Zahl) dann keine Primzahl.
Dies funktioniert bis zum bei int mit Zahlen bis 2 Mrd.-irgenwas. Hier mal der Pseudocode:
int n = 2;
int Zahl;
scanf(Zahl)
while Rest (!= 0)
{
Rest = Zahl%n
n++
}
Wenn Zahl == n dann Primzahl
Else keine Primzahl
ISt super schnell im Vergleich zum SIeb
