C++ Programm Primzahlen?

Hallo Zusammen,

ich lerne zurzeit die Programmierung in C und C++ für meine Studium.

Ich soll ein Programm entwickeln das die Primzahlen bis 100 ausgibt.

Dazu habe ich folgende Musterlösung. Allerdings verstehe ich noch nicht zu 100% was das Programm genau bewirkt. Erklärung vom Professor fehlen leider komplett.

Ich kennen das Prinzip der Anwendung von Arrays

Allerdings erschließt sich mir die Vorgehensweise des Programm nicht.

Gibt es jemanden der mir Zeile für Zeile erläutern kann was die einzelnen Programmzeilen für Berechnungen durchführen bzw bewirken?

Ich verlieren als kompletter Neuling doch noch sehr schnell die Übersicht, selbst wenn ich auf dem Papier die einzelnen Zeilen versuche nach zurechnen.

Soviel hab ich verstanden das der Index des Arrays mit 1 zugewiesen wird, wenn eine Primzahl vorliegt, ansonsten wird das Feld mit 0 beschrieben.

Vielen Dank für eure Hilfe

#include <stdio.h>
#define N 100

int main()
{
  int i, j, a[N+1];
  a[1] = 0;
  for (i = 2; i <= N; i++) a[i] = 1;
  for (i = 1; i <= N; i++)
    if (a[i]) printf("%d", i);
  for (i = 2; i <= N / 2; i++)
    for (j = 2; j <= N/i; j++)
      a[i * j] = 0;

  printf("\n Berechn. der Primzahlen < 100: \n");
  for (i = 1; i <= N; i++)
    if (a[i]) printf("\n %d", i);
  printf("\n Ende des Programms \n");
  return 0;
}

2 Antworten

geri3d

Nutzer, der sehr aktiv auf gutefrage ist

im Thema programmieren

01.09.2020, 14:50

C++ ist leider nicht meine Disziplin aber ich versuchs mal:

#include <stdio.h> // Standard Input Output

#define N 100 // Konstante N=100

int main() // ohne Worte

{

int i, j, a[N+1]; // Deklaration der Variablen

a[1] = 0; // 1=0 denn die erste Primzahl ist 2

for (i = 2; i <= N; i++) a[i] = 1; // Alle auf 1

for (i = 1; i <= N; i++) // Durchlauf

if (a[i]) printf("%d", i); // Falls a[i] gib i aus (verstehe ich nicht)

for (i = 2; i <= N / 2; i++) // Durchlauf 1. Instanz

for (j = 2; j <= N/i; j++) // Durchlauf verschachtelt

a[i * j] = 0; // alle Felder in a[] die keine Primzahl sind als sich restlos dividieren lassen auf 0

printf("\n Berechn. der Primzahlen < 100: \n"); // Text ausgabe

for (i = 1; i <= N; i++) // Durchlauf

if (a[i]) printf("\n %d", i); Falls a[i] ungleich 0 ist i eine Primzahl und wird ausgegeben

printf("\n Ende des Programms \n"); // Ohne Worte
return 0; // Tschüss

Woher ich das weiß:eigene Erfahrung

Diviil1

Beitragsersteller

01.09.2020, 16:06

Vielen Dank. Mit dem Ansatz deines Vorposter + deine Erläuterung helfen mir bestimmt weiter

bluebird5

01.09.2020, 14:11

Das ist ein Eratosthenes-Sieb. Das ist hier ganz gut erklärt - versuch erstmal den Algorithmus als Ganzes zu verstehen, bevor du dich an den Code selbst wagst. Vereinfacht gesagt wird hier anfangs davon ausgegangen, dass alle Zahlen im Array, die größer als 1 sind, eine Primzahl sind. Und dann werden alle Quadratzahlen (also 2*2, 2*3, 2*4, ... die Variablen i und j bei dir im Code) gestrichen. Was danach noch übrig bleibt, ist eine Primzahl.

KarlRanseierIII

01.09.2020, 15:23

Fast, nicht Quadratzahlen werden gestrichen, sondern alle ganzzahligen Vielfachen - Nach der Aussage mit der Quadrahzahl hast Du es exemplarisch richtig hingeschrieben).

Diviil1

Beitragsersteller

02.09.2020, 08:15

Der Algorithmus ist mir nun soweit klar geworden. Das hat die Sache deutlich vereinfacht. Eine Weiter frage hätte ich noch.

<<<<<for (i = 2; i <= N / 2; i++)<<<<<<

for (j = 2; j <= N/i; j++)

a[i * j] = 0;

der teil des Programms zwischen den Pfeilen, wozu dient der? Nach meinem Verständnis sollte das Programm auch ohne diesen Teil ablauffähig sein und die korrekten Zahlen liefern.. Ist dies zur Verringerung der Berechnungszeit ?

Vielen Dank

Diviil1

Beitragsersteller

02.09.2020, 08:29

@Diviil1

Ups ich meinte natürlich den Teil hier: for (i = 2; i <= N <<</ 2>>>; i++)

bluebird5

02.09.2020, 09:35

@Diviil1

Allgemein: probier solche Sachen aus. Wenn du i hier von 2 bis N laufen lässt, also

for (i = 2; i <= N; i++) {

, dann stürzt dein Programm ab, weil in

a[i * j] = 0;

irgendwann die Größe des Arrays überschreiten wird. Das müsstest du dann also vorher abfangen.

Mathematisch ganz richtig ist der Teil nicht, es würde reichen, wenn du i von 2 bis zur Wurzel (und nicht bis zur Hälfte) von N laufen lassen würdest. Das ist in dem verlinkten Skript auf Seite 4 so erklärt, warum es über der Wurzel keine Ergebnisse geben kann.

Neben der Sache mit den Abstürzen (die man durch eine einfache if-Bedingung abfangen könnte) macht man das also, damit der Algorithmus schneller durchläuft.

ralphdieter

02.09.2020, 17:55

@Diviil1

Ist dies zur Verringerung der Berechnungszeit ?

Nicht wirklich. Schau dir mal die innere Schleife für den letzten Wert i==N/2 an (angenommen, N ist gerade). Wegen N/i=N/(N/2)=2 steht da effektiv:

for (j = 2; j <= 2; j++)

das heißt, die Schleife läuft genau einmal durch. Für jedes größere i läuft j von 2 bis 1, wird also nicht mehr ausgeführt. Deshalb ist es unnötig (aber nicht falsch), die äußere Schleife weiter als N/2 gehen zu lassen.

Gilt das auch bei ungeradem N? Reicht hier i=(N-1)/2 als letzter Wert oder muss man vielleicht doch manchmal den nächsten Wert i=(N+1)/2 mitnehmen? Die meisten Programmierer werden dieses Problem entweder übersehen oder an einem Beispiel verifizieren, z.B. für N=9:

i=2...9/2=4 ⇒ j=2...9/4=2 — noch ein Durchlauf.
i=2...4+1=5 ⇒ j=2...9/5=1 — kein Durchlauf mehr.

Sieht also gut aus. Aber wenn der Code in einem Herzschrittmacher oder einer Raketensteuerung läuft, muss ein mathematischer Beweis dafür her, dass N/2 in der äußeren Schleife wirklich immer als Obergrenze ausreicht.

ralphdieter

02.09.2020, 18:00

@bluebird5

dann stürzt dein Programm ab, weil in

a[i * j] = 0;

irgendwann die Größe des Arrays überschreiten wird

Nein. Die innere Schleife geht nur bis j=N/i. Also ist j*i≤(N/i)*i≤N. Das Array a ist N+1 lang, also passt a[i*j] immer.

Diviil1

Beitragsersteller

01.09.2020, 16:05

Danke für den Hinweis. Das ist aufjedenfall ein guter Ansatzpunkt der mir bestimmt weiterhilft.

Ähnliche Beiträge

Primzahlen mit Java?

Hey Leute,

Ich würde gerne ein Programm in Java (BlueJ) schreiben, welches mit Hilfe von for und If (kein while!) die Zahlen von 1-100 nach Primzahlen prüft und die Primzahlen ausgibt.

Wie macht man das?

Danke im Voraus ;)

...zum Beitrag

c# Primzahlen?

Hey liebe Community,

ich hätte da mal eine Frage. Ich habe die Möglichkeit, meinen Code etwas zu verändern. Bisher habe ich mit dem Code geprüft, ob die Eingabe des Benutzers eine Primzahl ist. Wie könnte ich es machen, dass z.B. der Benutzer eine Zahl eingibt (4) und die ersten vier Primzahlen ausgegeben werden?

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace Primzahlen
{
  class Program
  {
    static bool Primzahl(int primzahl)
    {
      bool ergebnis = false;
      int zähler = 0;

      for (int i = 1; i <= primzahl; ++i) // Zahl wird durch Teiler geteilt
      {
        if (primzahl % i == 0) //Teilung ohne Restwert, dann für 1 zum Zähler hinzufügen
        {
          zähler = ++zähler;
        }
      }

      if (zähler == 2) //Wenn Zahl nur durch sich und 1 teilbar ist, Ausgabe (Da Zähler auf 2 ist)
      {
        ergebnis = true;
      }

      return ergebnis;
    }

    static void Main(string[] args)
    {
      Console.Title = "Primzahlen";
      StreamWriter sw = new StreamWriter("Primzahlen.txt");

      Console.WriteLine("Geben Sie eine Zahl ein");
      string eingabe = Console.ReadLine();
      sw.WriteLine(eingabe);
      sw.Close();

      String dateiName = "Primzahlen.txt";
      StreamReader reader = null;
      int zahl = 0;
    
      try
      {
        reader = new StreamReader(dateiName);
        string zeile = reader.ReadLine();
        zahl = Convert.ToInt32(zeile);
      }
      catch (Exception ex)
      {
        Console.WriteLine(ex.Message);
      }
      finally
      {
        if (reader != null)
          reader.Close();
      }

      if (Primzahl(zahl))
      {
        Console.WriteLine("Das ist eine Primzahl");
      }
      else
      {
        Console.WriteLine("Keine Primzahl");
      }

      Console.ReadLine();
    }
  }
}

Vielen Dank!

...zum Beitrag

Wie überprüft man in C, ob eine Zahl eine Primzahl ist?

include
int main(){ 
  int counter = 1; 
  int AusgegebeneZahl;
  int EingegebeneZahl = 5;
  while(counter < EingegebeneZahl-1){
    AusgegebeneZahl = EingegebeneZahl/(EingegebeneZahl-counter);
    printf("%i\n", AusgegebeneZahl);
    if (AusgegebeneZahl%counter == 0) {
      printf("Zahl ist keine Primzahl");
    }
  counter++;
  }
}

Wo liegt mein Fehler?

...zum Beitrag

Java Primzahlen Programm

Hey Leute, ich habe mal wieder eine Java-Aufgabe, bei welcher ich den Fehler nicht finde. Ich hoffe ihr könnt mir irgendwie weiterhelfen.

public class PrimeNumbers {

static int x = 1000;
private static boolean[] Primes = new boolean[x];

// Hier ist der "statische Konstruktor"
static {
}

private static boolean checkPrime(int number) {

    return false;
}

public static boolean isPrime(int number) {
    int limit=1000;
    int zahl;      
    int zaehler;   
    boolean primzahl; 

    for (zahl = 2; zahl <= limit; zahl++) {
        primzahl = true;

        for (zaehler = 2; zaehler <= zahl/2; zaehler++) {
            if (zahl % zaehler == 0) {
                primzahl = false;
              break;
            }

        }

        if (primzahl) {
            return true;
        }
    }
    return false;
}

Die Primzahlen, welche zu überprüfen sind werden in einer anderen Methode übergeben und abefragt. Ich habe hier das Problem, dass er mir entweder immer true oder immer false returned, egal ob es nun eine Primzahl ist oder nicht. Ich komme einfach nicht weiter, egal wie ich es drehe und wende. Ich hoffe ihr könnt mir weiterhelfen.

Grüße Dubsepp

...zum Beitrag

C program for schleife?

Ich habe diese Anweisung bekommen:

Übung for schleife:

Das Programm soll die Summe, Mittelwert, MAX und MIN-Wert einer eingegebenen Zahlenfolge berechnen uns ausgeben

Wenn der User keine Zahl eingibt und einfach mit Enter bestätigt, soll das einlesen abgebrochen werden.

-----------------------------------------------------------------------------------------------------------------------------------

und ich habe es so gelöst:

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

int main()
{
  int a,b;


  printf("Geben sie die Zahl a: ");
  scanf("%i", &a);

  printf("Geben sie die Zahl b: ");
  scanf("%i", &b);

  int max = a;
  int min = b;

  if(max < b) {
    max = b;
    min = a;
  };

  int mittelwert = a/b;
  int summe = a+b;

// ignorier die for-schleife
  for (min; min < max; min++) {

  };

  printf("Max: %i \n Min: %i \n Mittelwert: %i \n Summe: %i \n", max, min, mittelwert, summe);

  return 0;
  }

Jetzt zu meiner frage, wo und wie soll ich eigentlich die for schleife benutzten wenn ich eine nicht mal brauche, wir haben keine Arrays etc. gelernt...

...zum Beitrag

Java: Wie funktioniert dieser Primzahlengenerator?

public static List<Integer> generateNumbers(int border) {
  List<Integer> finalList = new ArrayList<>();
  boolean[] bool = new boolean[border];

  for (int i = 0; i < bool.length; i++) {
    bool[i] = true;
  }

  /////////
  for (int i = 2; i < Math.sqrt(border); i++) {
    if (bool[i] == true) {
      for (int j = (i * i); j < border; j = j + i) {
        bool[j] = false;
      }
    }
  }
  ////////

  for (int i = 2; i < bool.length; i++) {
    if (bool[i] == true) {
      finalList.add(i);
    }
  }

  return finalList;
}

Mir geht es vor allem um den Bereich, welcher in den ///////// drinnen liegt, wo ich die Nicht-Primzahlen herausfische. Kann mir jemand diese for-Schleife Schritt für Schritt erklären?

...zum Beitrag

C# Primzahlen ausgeben - Problem!

Hey! Mein Problem ist dieses: Ich programmiere gerade in C# und möchte ein Programm schreiben, dass mir die ersten 100 Primzahlen berechnet und dann ausgibt. Nur habe ich das Problem, dass ich alles geschreiben habe, aber die Konsole gibt nichts aus. Was ist mein Fehler?

Hier mein Code:

using System; using System.Collections.Generic; using System.Linq; using System.Text;

namespace ConsoleApplication1 { class Program { static void Main(string[] args) { //Übung 6 int i, Zähler; Zähler = 0;

        Console.WriteLine("*** Die ersten 100 Primzahlen ***\n");
        Console.Write("2" + "\t");

        for (i = 3; Zähler == 99; i+=2)
        {
            int j = 2;

            while (i % j != 0 && j <= i - 1)
            {
                j++;
            }

            if (j == i)
            {
                Console.Write(i + "\t");
                Zähler ++;
            }
        }

        Console.ReadLine();
    }
}

}

Danke im Voraus! :)

...zum Beitrag

In C: Celsius in Fahrenheit?

Moin,

ich habe ein Programm geschrieben, welches Celsius in Fahrenheit umrechnet. Jedoch bekomme ich nicht die richtigen Ergebnisse, da ich ja rein theoretisch die Ergebnisse der Rechnung (Formel für Umrechnung: Temp(in Celsius) * 9/5 + 32 in einer float-Variable speichern müsste, oder?

Hier meine Header:

#ifndef TEMPERATURE
#define TEMPERATURE

#define MAX_LENGTH 10

#define converter(c)((c * (9 / 5)) + 32)

double output_temperatures(double temp[]);
int string_length(double temp[]);
double widening(double temp2[]);
/* double appendix(double temp3[], temp4[]); */

#endif

Hier meine Funktionen:

#include "aufgabe2930b.h"
#include <stdio.h>

double output_temperatures(double temp[])
{
  int i;
  printf("Temperaturen in Fahrenheit: ");

  for (i = 0; i < string_length(temp); ++i) {
    if (temp[i] <= 100 && temp[i] >= -273.15) {
      printf("%f  ", converter(temp[i]));
    }
    else {
      printf("Falsche Eingabe! ");
      break;
    }
  }

  printf("\n");
  return 0;
}

int string_length(double temp[])
{
  int i = 0;
  int length = 0;

  while (temp[i] != '\0') {
    ++length;
    ++i;
  }

  return length;
}

double widening(double temp[])
{
  int i = 0;

  while (i < MAX_LENGTH - 1) {
    if (temp[i] == '\0') {
      printf("Bitte anzuhängende Temperatur eingeben: ");
      scanf("%lf", &temp[i]);
      temp[i + 1] = '\0';
      break;
    }
    else {
      ++i;
    }
  }

  for (i = 0 ; i < string_length(temp); ++i) {
    if (temp[i] <= 100 && temp[i] >= -273.15) {
      printf("%f  ", converter(temp[i]));
    }
    else {
      printf("Falsche Eingabe! ");
      break;
    }
  }

  return 0;
}

Hier meine main:

#include <stdio.h>
#include "aufgabe2930b.h"

int main(void)
{
  double temp[MAX_LENGTH] = { 1, 2 };
  output_temperatures(temp);
  widening(temp);

  return 0;
}

...zum Beitrag

Probleme mit C-Programmierung: Zahlen sortieren?

Hallo, ich habe folgendes Programm geschrieben und komme einfach nicht weiter. Das Programm zählt die Buchstaben einer .txt Datei und gibt ebenso deren Häufigkeit an. Ich soll jetzt noch die Anzahl der Buchstaben beginnen mit der größten Zahl sortieren. Die Buchstaben müssen dabei auch stimmen und natürlich die Häufigkeit. Kann mir jemand dabei helfen?

So weit bin ich gekommen, eine Beispiel txt Datei wurde implementiert. Ich programmiere mit Codeblocks.

#include <stdio.h>

include

char dateiname[40]; int anweisung1;

int main(int argc, char **argv) { if (argc != 2) { printf("Der Dateiname fehlt\n"); return 0; }

FILE *fp = fopen(argv[1], "r");
if (fp == NULL)
{
    printf("Die Datei kann nicht geoeffnet werden\n");
    return 0;
}

double anzahl[26] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
int gesamt = 0;


while (1) //Zähschleife
{
    int buchstaben = fgetc(fp);
    if (buchstaben < 0)
    {
        break;
    }
    if (buchstaben >= 'A' && buchstaben <= 'Z') //Zählschleife für Großbuchstaben
    {
        anzahl[buchstaben - 'A']++;
        gesamt++;
    }
    else if (buchstaben >= 'a' && buchstaben <= 'z')
    {
        anzahl[buchstaben - 'a']++; //Zähschleife für Kleinbuchstaben
        gesamt++;
    }
}


fclose(fp);

int anweisung;
printf("Dieses Programm zaehlt die die Buchstaben in einer .txt Datei\nund gibt die Haeufigkeit der Buchstaben an\n");
printf("Sie haben jetzt die Auswahl zwischen:\n");
printf("1. Die .txt Datei mit printf in der Konsole auszugeben\n");
printf("2. Eine neue .txt Datei zu speichern\n\n");
scanf("%d", &anweisung);

switch(anweisung)
{
case 1:
    printf("Die Gesamtzahl der Buchstaben lautet: %d\n",gesamt);

    int i;
    for (i = 0; i < 26; i++)
    {
        printf("%c : %0.lf", (i + 'A'), anzahl[i]);
        double prozente = anzahl[i]*100/gesamt;
        printf("\tHaeufigkeit: %.2lf%%\n",prozente);
    }
    return 0;

case 2:

    printf("\nBitte geben Sie den Dateinamen mit .txt an:\n\n");
    scanf("%s", dateiname);
    printf("\nIhre Datei heisst: %s.\n", dateiname);

    FILE* fp;
    fp = fopen(dateiname,"w");
    fprintf(fp,"Die Gesamtzahl der Buchstaben lautet: %d\n",gesamt);

    for (i = 0; i < 26; i++)
    {
        fprintf(fp,"%c : %0.1f\t  ", (i + 'A'), anzahl[i]);
        double prozente = anzahl[i]*100/gesamt;
        fprintf(fp,"Haeufigkeit: %.2lf%%\n",prozente);
    }
    return 0;
    fclose(fp);
}

}

...zum Beitrag

Java: Ich will mir alle Primzahlen bis 100 ausgeben, jedoch gibt mir das Programm nur die Zahlen bis 100 aus. Wo liegt das Problem?

Hi,

ich bin in Java noch so ziemlich am Anfang und habe soeben mir überlegt, ein Programm zu schreiben, welches in der Lage sein sollte, mir alle Primzahlen bis 100 auszugeben.

Allerdings gibt es mir alle Zahlen bis 100. Wo liegt das Problem?

import java.util.*;

public class test {
  public static void main(String[] args) {
    long pri1 = 2;
    long pri2 = 1;
    boolean ip = true;

    for (pri1 = 2; pri1 < 100; pri1++) {
      for (pri2 = 1; pri2 < pri1; pri2++) {
        if (pri1 % pri2 == 0) {
          ip = false;
          break;
        } // end of if 
      } // end of for
    
      if (ip = true) {
        System.out.println(pri1);
      } // end of if
    } // end of for
  }
}

Ich freue mich auf hilfreiche Antworten. 😊

...zum Beitrag

Palindrom mit C-Programmieren überprüfen?

Ich habe eine Aufgabe bekommen, wo ich mit einem C-Code überprüfen muss, ob das Wort oder ein Satz ein Palindrom ist. Ich habe folgendes ausprobiert, aber da sind paar Fehler drin, ich komm nicht weiter:

#include <stdio.h>
#include <string.h>

int main (){  
  char text[255];
  int len =0;
  int i;
  int j;
  int z;
  char neu;
   
  printf("Bitte text eingeben");
  fgets(text, 255, stdin);   
  len = strlen(text);
   
  for (i=0; i != len; i++)
    if (text[i] >= 'A' && text[i] <= 'Z'){
      text[i] += 32;
    }
   
  for (j = len; j >= 0; j--)
    printf("%c",text[j]);
   
  printf("\n");
   
  if (text[j] == text[i]) {
      printf("palindrom");
    }
     
    else {
      printf("kein palindrom");
    }
}

...zum Beitrag

Java - Primzahlen ermitteln

Soll zwischen 1 und 100 alle Primzahlen in Java ermitteln. Lasse ich das Programm laufen wird keine Zahl ausgegeben. Ich habe festgestellt, dass bei jeder Zahl primzahl == false ist. Zu beginn war der boolean primzahl true. Was habe ich falsch gemacht?

System.out.println ("Primzahlen:");

for (i=1 ;i<=100 ;i++ ) {
  if (i==1) {
    primzahl = false;
  } // end of if
    else {
    for (j=2 ;j<i ;j++ ) {
      if (i % j == 0) {
        primzahl = false;
      } // end of if
    } // end of for
  } // end of if-else
  if (primzahl == true) {
    System.out.println (i);
  } // end of if
} // end of for

...zum Beitrag

"Primzahlen-prüfer" programmier (C#)?

Das Programm wurde in c# programmiert. Ich wollte ein etwas programmieren, das die Startzahl (endlos) immer um 1 addiert und prüft ob diese Zahl eine Primzahl ist oder nicht. Habe den Quellcode unter diesem Text geschrieben, aufm Display wird aber nur "ist keine Primzahl" angezeigt. Wüsste jemand wie man dieses Promblem fixen könnte?

static void Main(string[] args) {    
    int zahl = 1;
        int zähler = 0;

        while (true)
        {
            for (int prüfer = 1; prüfer <= zahl; prüfer++)
            {
                if (zahl % prüfer == 0)
                {
                    zähler++;
                }

            }
            if (zähler == 2)
            {
                Console.WriteLine(zahl + " ist Primzahl");
            }
            else
            {
                Console.WriteLine(zahl + " ist keine Primzahl");
            }
            zahl++;

        }

    }

...zum Beitrag

Primzahlenerkennungsprogramm Python?

Hallo habe hier ein Programm mithilfe einer Funktion geschrieben,welche erkennen soll ob die eingegebene Zahl eine Primzahl ist.Allerdings kann ich das Unterprogramm nicht aufrufen weil eine Fehlermeldung kommt.Könntet ihr mir bitte helfen.

Mein Programm:

a = int(input("Zahl ? " )

def primzahl (a) :

for i in range (0,a):

if a == 1:

return False

elif a%i == 0 :

return False

else:

return True

primzahl(a)

...zum Beitrag

Was möchtest Du wissen?

Deine Frage stellen