Primzahlgenerator in C++

1. Primzahlen
2. Generieren Sie Primzahlen in C++
3. Verwenden Sie die sqrt()-Methode, um Primzahlen in C++ zu generieren

Dieses schnelle Programmier-Tutorial führt durch die einfache, intuitive Methode und eine effiziente Quadratwurzelmethode zum Erzeugen aller Primzahlen innerhalb eines bestimmten Bereichs.

Primzahlen

Eine Primzahl ist eine Zahl, die nur durch eins oder durch sich selbst teilbar ist; Beispielsweise ist 17 eine Zahl, die nur durch eins oder sich selbst teilbar ist. Der einzig mögliche Faktor für eine Primzahl P ist P * 1.

Schauen wir uns die Menge der Primzahlen an:

Set of Prime Numbers = {2, 3, 5 , 7, 11, 13, 17, 23, .....,89, 97, .... }

In C++ können wir solche Szenarien codieren und die Primzahlen innerhalb eines bestimmten Bereichs generieren und sogar prüfen, ob eine Zahl eine Primzahl ist oder nicht.

Generieren Sie Primzahlen in C++

Die Logik hinter der Überprüfung, ob eine Zahl eine Primzahl ist, besteht darin, ihren Modul mit allen Zahlen bis zur Hälfte dieser Zahl zu überprüfen. Wenn ihr Modul bei einer der Zahlen 0 ist, dann ist die Zahl keine Primzahl; andernfalls ist es prim.

Schauen wir uns die einfachste und intuitivste Methode an:

#include <iostream>
using namespace std;

int main() {
  int start = 0, end = 100, n;
  bool ifPrime = true;

  cout << "Prime numbers in between " << start << " and " << end
       << " are the following: " << endl;

  while (start < end) {
    ifPrime = true;

    if (start == 0 || start == 1) {
      ifPrime = false;
    }

    for (n = 2; n <= start / 2; ++n) {
      if (start % n == 0) {
        ifPrime = false;
        break;
      }
    }
    if (ifPrime) cout << start << ", ";

    ++start;
  }

  return 0;
}

Wir haben im obigen Codesegment zwei Variablen genommen, start und end. Die Variable start wird auf Null initialisiert und die Variable Ende wird auf 100 initialisiert, da wir Primzahlen von 0 bis 100 benötigen.

Dieser Bereich kann jederzeit geändert oder auch vom Benutzer als Eingabe genommen werden.

Wir haben eine Schleife von start bis Ende erstellt; In dieser Schleife haben wir eine weitere for-Schleife gemacht, um zu prüfen, ob die start-Zahl durch die Zahlen bis zur Hälfte dieser Zahl teilbar ist. Denn für eine Nicht-Primzahl N kann es nur Faktoren mit den Zahlen a und b geben, so dass a*b mit a<N/2 und b<N/2.

Wenn also die innere for-Schleife das n die Hälfte des start-Werts erreichen lässt, endet die Schleife und die Zahl wird in Zeile 25 ausgegeben, da ifprime immer noch true ist. Wenn jedoch irgendein Wert von n den start-Wert richtig teilt, wird die Bedingung in Zeile 19 true, was ifprime auf false setzt und die for-Schleife beendet.

Ausgang:

Verwenden Sie die sqrt()-Methode, um Primzahlen in C++ zu generieren

Die zuvor besprochene einfache Berechnungsmethode für Primzahlen war ineffizient, da wir immer noch bis zur Hälfte der Zahl dividieren müssen, um zu prüfen, ob es sich um eine Primzahl handelt oder nicht. Wir können jedoch mathematische Tatsachen ausnutzen, um die Komplexität unserer Programmlaufzeit zu reduzieren.

Das Programm hilft dabei, dass damit ein Faktor a*b gleich einer Zahl N ist, entweder a oder b kleiner oder gleich der Quadratwurzel von N sein muss. Zum Beispiel sind für 36 die möglichen Faktorpaare (9*4), (18*2), (12*3), (6*6), also hat jedes Paar a oder b kleiner als die Quadratwurzel von 36.

Um also eine Zahl N als keine Primzahl abzulehnen, müssen wir nur prüfen, ob sie durch eine Zahl kleiner als die Quadratwurzel von N teilbar ist oder nicht. Ist dies nicht der Fall, bedeutet dies, dass die Zahl eine Primzahl ist.

Lassen Sie uns nun das Szenario codieren:

#include <math.h>

#include <iostream>
using namespace std;

int main() {
  int start = 0, end = 100, n;
  bool ifPrime = true;

  cout << "Prime numbers in between " << start << " and " << end
       << " are the following: " << endl;

  while (start < end) {
    ifPrime = true;

    if (start == 0 || start == 1) {
      ifPrime = false;
    }

    for (n = 2; n <= sqrt(start); ++n) {
      if (start % n == 0) {
        ifPrime = false;
        break;
      }
    }
    if (ifPrime) cout << start << ", ";

    ++start;
  }

  return 0;
}

Wir haben eine Schleife von start bis Ende erstellt, und in dieser Schleife ziehen wir eine Quadratwurzel aus der Zahl, die die Zahl für die Kürzung der inneren Schleife ist.

Eine innere Schleife prüft, ob die aktuelle Zahl durch eine beliebige Zahl bis zu ihrer Quadratwurzel teilbar ist. Wenn nicht, drucken wir es als Primzahl.

Ausgang: