Code in C schreiben, der auf primzahl prüft?

Folgendes Problem: ich will einen Coode in C schreiben, der mir sagt, ob die Zahl eine Primzahl ist oder nicht. Dazu will ich eine Zahl „so“ überprüfen: ich gebe ihm die Zahl vor, und er soll mit Mod überprüfen, ob die Zahl einen Rest hat; falls nein, teile ich die nochmal so klein wie es geht

als Beispiel habe ich die Zahl 105 genommen

Bild zum Beitrag

in der zweiten Zeile soll ausschließlich ein ja ausgegeben werden, falls die Variable „number“ eine Primzahl gespeichert ist, falls nicht, dann soll ein nein ausgegeben werden und es sollen auch nur 2 zeilen ausgegeben werden

leider fehlt mir das wissen und Verständnis - sofern ich keinen Denkfehler hatte - wie ich meinen Gedankengang in einen Code überführen kann

wäre sehr dankbar für eine Anleitung mit kurzen erklärschritten

danke!

4 Antworten

CarinaSchoppe

20.10.2021, 22:23

Der ganz klassische Ansatz geht in Pseudocode so:

Zahl = Eingabe
Für test = 2 bis Wurzel(Zahl):
  Wenn Zahl modulo test gleich 0 ist:
    keine Primzahl, Schleife abbrechen
Falls Schleife nie abgebrochen wurde, ist Zahl eine Primzahl

Du testest deine Zahl nacheinander mit dem gesamten Zahlenbereich möglicher Teiler durch. Wenn eine Zahl ein Teiler ist, ist der Modulo = 0 und du weißt, dass es keine Primzahl ist. Du könntest natürlich mit dieser Methode auch alle Primfaktoren bestimmen. Etwas optimieren könne man noch, indem man den Teiler 2 separat testet und dann nur alle ungeraden durchgeht.

Eine andere Möglichkeit ist das bereits angesprochene Sieb des Erastosthenes. Das eignet sich, um Primzahlen eines ganzen Zahlenbereiches zu finden. Dabei erzeugst du ein Array von bool-Werten (bzw. in c int-Werte) in der Größe des Zahlenbereichs (von 0 beginnend) und gehst alle Vielfachen durch und setzt die Felder auf false.

Woher ich das weiß:Studium / Ausbildung – info studium

Schachpapa

20.10.2021, 22:29

Etwas optimieren könne man noch, indem man den Teiler 2 separat testet und dann nur alle ungeraden durchgeht.

Oder 2 und 3 vorab und dann ab 5 abwechselnd in 2er und 4er Schritten:

5,7, 11,13, 17,19, 23,25, 29,31, usw.

veeQuZ

Fragesteller

20.10.2021, 22:44

Kann leider dem nicht folgen, was du geschrieben hast und in welchem Zusammenhang Wurzeln jetzt darin stehen

Danke, könntest du das bitte noch etwas erläutern?

Angenommen, ich möchte die Zahl 105 testen, also

int main () {

int nummer 105 = 105;

printf(„Ist d% eine primzahl?\n“, nummer);

n= 1;

n+1;

if 102 % n =/ 0 -> prim

else 102 % n +1

wäre das so ganz grob korrekt? Mir fällt leider das „Vokabular“, das korrekt auszudrücken

Könntest du das bitte irgendwie ergänzen/korrigieren? ._.
danke!

Schachpapa

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

Mathematik

20.10.2021, 22:24

Probiere in einer Schleife mögliche Teilerkandidaten aus. Wenn bei einer anderen Zahl als 1 und der zu prüfenden Zahl der Rest 0 herauskommt, ist es keine Primzahl und du kannst aufhören. Bei deinem Beispiel wäre das schon bei 3 der Fall.

Wenn das funktioniert, kannst du dir Gedanken machen, ob du vielleicht nicht alle Zahlen zwischen 2 und n-1 ausprobieren musst.

veeQuZ

Fragesteller

20.10.2021, 22:41

Danke, könntest du das bitte noch etwas erläutern?
Angenommen, ich möchte die Zahl 105 testen, also

int main () {

int nummer 105 = 105;

printf(„Ist d% eine primzahl?\n“, nummer);

n= 1;

n+1;

if 102 % n =/ 0 -> prim

else 102 % n +1

wäre das so ganz grob korrekt? Mir fällt leider das „Vokabular“, das korrekt auszudrücken

wäre das in Ordnung?

Schachpapa

20.10.2021, 22:48

@veeQuZ

int main () {

int nummer = 105;

printf(„Ist %d eine primzahl?\n“, nummer);

teiler = 1;
Schleifenanfang <- Hier musst du mal nachdenken
  {
  teiler = teiler+1;
  rest = nummer % teiler;
  if (rest == 0) {
    // nicht prim, abbrechen
  }
// Wenn kein teiler mit rest == 0 gefunden, 
// dann ist es eine Primzahl
// (außer wenn teiler == nummer, 
// denn das geht ja immer glatt auf)

Ich will dir nicht alles vorschreiben, dann hast du ja keinen Lerneffekt. Programmieren lernt man nicht vom Zugucken, sondern vom Selbermachen. Genau wie Radfahren.

veeQuZ

Fragesteller

20.10.2021, 22:56

@Schachpapa

Danke, das hatte ich auch nicht erwartet.

Der Schleifenanfang ist ja der Anfang, wenn die schleife nochmals durchlaufen wird, und die wird ja nur durchlaufen, wenn die Zahl prim ist, richtig?

Schachpapa

20.10.2021, 23:00

@veeQuZ

Ja, aber das weißt du ja vorher nicht.

Die Schleife sollte mindestens so oft durchlaufen werden, bis klar ist, ob es sich um eine Primzahl handelt oder nicht. Und das weißt du spätestens dann, wenn du mit teiler bei der zu prüfenden Zahl (nummer) angekommen bist und bis dahin keine Zahl (teiler) gefunden hast, bei der der rest 0 bleibt. Eigentlich auch schon vorher, aber es muss ja nicht gleich im ersten Anlauf optimal sein.

veeQuZ

Fragesteller

20.10.2021, 23:03

@Schachpapa

Danke, d.h., dass dann der Schleifenanfang nummer / teiler ist?

und dann eine else-Schleife folgt?

Schachpapa

20.10.2021, 23:18

@veeQuZ

Else-Schleife? Das habe ich noch nie gehört, wohl das Gegenstück dazu.

Du stehst noch sehr am Anfang der Programmierung, nicht wahr? Und dann C als erste Programmiersprache, du Armer!

Der Schleifenanfang wäre:

while (teiler < nummer) {

Das ganze Ding kann man auch formulieren als:

int nummer = 105; // das sollte man eingeben können
int teiler = 1;
int rest = 1; // sonst wird die Schleife nicht betreten

while (teiler < nummer && rest > 0) {
  teiler = teiler + 1;
  rest = nummer % teiler;
}

if (teiler < nummer) 
  printf("%d ist nicht prim\n",nummer);
else // dann ist teiler == nummer
  printf("%d ist prim\n",nummer);

Verstehst du das oder brauchst du Erklärungen?

Den Fall nummer==1 müsste man gesondert behandeln, denn 1 ist keine Primzahl.

veeQuZ

Fragesteller

20.10.2021, 23:24

@Schachpapa

Kann man so sagen haha, 1. Semester Studium

Das ist aber einleuchtend, nachdem man das so gehört hat.

Nur int rest = 1 verstehe ich nicht, wieso wird die schleife nicht betreten?

genauso wie das doppel und-zeichen bei nummer und und rest

Könntest Du das nochmal erklären, bitte?

Schachpapa

20.10.2021, 23:27

@Schachpapa

Ich gehe jetzt schlafen, daher noch kurz die Erklärung:

nummer ist 105, teiler ist 1, rest auch.

Zu Beginn der Schleife gilt: 1 < 105 und 1 > 0 also Schleifenrumpf ausführen

teiler wird 2, rest wird 105%2 also 1

Schleifenbedingung prüfen: 2 < 105 und 1 > 0 also Schleifenrumpf ausführen

teiler wird 3, rest wird 105%3 also 0

Schleifenbedingung prüfen: 3 < 105 aber 0 == 0 also fertig.

3 < 105 also keine Primzahl.

Schachpapa

20.10.2021, 23:31

@veeQuZ

Nur int rest = 1 verstehe ich nicht, wieso wird die schleife nicht betreten?

genauso wie das doppel und-zeichen bei nummer und und rest

rest muss mit (irgend)einem Wert >0 vorbesetzt werden, sonst ist die Schleifenbedingung von vornherein nicht erfüllt und es würde direkt nach der Schleife weiter gehen.

Dass Doppel-& bedeutet, dass sowohl teiler < nummer als auch rest > 0 gelten muss, damit der Schleifenrumpf ausgeführt wird. Wenn eine der beiden Bedingungen false ergibt, geht es nach der Schleife weiter. Wenn die erste Bedingung false ergibt, wird beim Doppel-& die zweite erst gar nicht geprüft.

So, Nacht jetzt!

veeQuZ

Fragesteller

21.10.2021, 15:28

@Schachpapa

Hi, danke, das habe ich soweit verstanden.

Mein code sind folgendermaßen aus:

#include <stdio.h>

int main() {

{int nummer = 22201;

int teiler = 1;

int rest = 1;

while (teiler < nummer && rest > 0){

teiler = teiler +1;

rest = nummer % teiler;

}

if (teiler < nummer)

printf("%d ist nicht prim\n",nummer);

else

printf("%d ist prim\n",nummer);

aber da kommt folgende fehlermeldung:

error: use of undeclared identifier 'teiler'

if (teiler < nummer)

prim.c:15:14: error: use of undeclared identifier 'nummer'

if (teiler < nummer)

prim.c:16:31: error: use of undeclared identifier 'nummer'

printf("%d ist nicht prim\n",nummer);

prim.c:18:25: error: use of undeclared identifier 'nummer'

printf("%d ist prim\n",nummer);

prim.c:23:1: error: expected '}'

prim.c:3:12: note: to match this '{'

int main() {

5 errors generated.

Schachpapa

21.10.2021, 16:15

@veeQuZ

#include <stdio.h>
int main() {
    {int nummer = 22201;
    int teiler = 1;
    int rest = 1;
    while (teiler < nummer && rest > 0){
        teiler = teiler +1;
        rest = nummer % teiler;
    }
    }
    if (teiler < nummer)
      printf("%d ist nicht prim\n",nummer);
    else
      printf("%d ist prim\n",nummer);

Vor "int nummer = ..." steht eine {-Klammer, die da nicht hingehört. Ebensowenig das Gegenstück dazu über "if (teiler < ..."

Am Ende fehlt die schließende Klammer, die bei main geöffnet wird.

Durch die beiden zu löschenden Klammern hast du einen Block geschaffen, in dem die Variablen nummer, teiler und rest loka sind. Deshalb bekommst du außerhalb dieses Blocks die 4 Fehlermeldungen über "undeclared identifier". Der letzte Fehler ist die fehlende schließende Klammer am Ende.

Schachpapa

21.10.2021, 16:28

@Schachpapa

Und wenn das läuft, änderst du die while Bedingung zu:

while (teiler*teiler < nummer && rest > 0) {

und nach der Schleife

if (rest == 0)

Dann läuft es insbesondere bei sehr großen Zahlen schneller. Damit man richtig große Zahlen hat, müsste man wohl den Datentyp von zahl, teiler und rest auf "long int" oder "long long int" ändern.

PcCraftGuy123

20.10.2021, 22:24

evtl mit % teilung mit Rest und dann probierst du das für zahl%2 zahl%3 zahl%7 usw aus und schaust ob das Ergebnis 0 ist, sonst primzahl

codinghelp

Nutzer, der sehr aktiv auf gutefrage ist

im Thema programmieren

20.10.2021, 22:23

Eine Zahl kann kein Rest haben - eine Division schon

Im einfachsten Ansatz versuchst du einfach deine Zahl durch alle Zahlen vorher zu teilen, wenn immer ein Rest übrig bleibt ist es ne Primzahl

Einfache Verbesserungen: Nur bis Wurzel(n) gehen, nur durch Primzahlen teilen

Falls ja, ist diese Zahl eine Primzahl

leider fehlt mir das wissen und Verständnis - sofern ich keinen Denkfehler hatte - wie ich meinen Gedankengang in einen Code überführen kann

wäre sehr dankbar für eine Anleitung mit kurzen erklärschritten

danke!

...zur Frage

Primzahl - Möglichkeiten um eine Zahl zu überprüfen (Nur bis wurzel(x))?

Hi,

ich habe mir grade ein C++ Code angeschaut womit man Zahlen ueberpruefen kann ob sie eine Primzahl sind oder nicht.

Der Code funktioniert...

Wenn die Zahl n zu überprüfen ist, prüft der code ob die Zahlen in den Grenzen von 2 bis wurzel(n) durch eine andere Teilbar ist. Wenn ja => Keine Primzahl, wenn nicht => Primzahl.

Meine Frage ist, warum reicht es aus wenn man die Grenzen von 2 bis wurzel(n) überprüft. Warum muss man nicht 2 bis n überprüfen?

...zur Frage

Frage zu struct array in C, warum wird Zahl nicht in Konsole ausgegeben?

Hallo,

ich habe eine Frage zu struct array in C:

Version1: Wenn ich die Zahl 1 so (dynamisch mit malloc) in dem struktur array daten speichere und in der Konsole ausgebe dann klappt es.

# include<stdio.h>
# include<string.h>
# include<stdlib.h>
# include<math.h>
# define MAX_ANZAHL 10

typedef struct messwert
{
    int number;
    
} MESSWERTE;


int main()
{

   MESSWERTE *daten =malloc(MAX_ANZAHL*sizeof(daten));
   daten[0].number=1;
   printf("%d\n", daten[0].number);

    return 0;
}

Version2: Aber wenn ich die Zahl 1 mit einem Struktur Array mit einer festen Größe speichere und printen will, kommt da in der Konsole nix.

# include<stdio.h>
# include<string.h>
# include<stdlib.h>
# include<math.h>
# define MAX_ANZAHL 10

typedef struct messwert
{
    int number;
    
} MESSWERTE;


int main()
{
   MESSWERTE *daten [MAX_ANZAHL];
   daten[0]->number=1;
   printf("%d\n", daten[0]->number);
   
    return 0;
}

Meine Frage ist wieso ich bei der Version 2 die Zahl 1 nicht in der Konsole ausgegeben wird.

Ich komme leider selbst nicht drauf. Danke!

...zur Frage

c# prüfen ob Primzahl?

Ich soll in C# überprüfen, ob eine Zahl eine Primzahl ist.

So ist der Code in meinem Programm, der das prüfen soll:

  if (zahl/zahl ==1 &&zahl/1 == zahl)
  {
    Console.WriteLine("Es handelt sich um eine Primzahl.");
  }
else
  {
    Console.WriteLine("Es handelt sich um keine Primzahl.");
  }

Ich möchte ihn aber so abändern, das die Zahl eine Primzahl ist, wenn nur die Bedingung gilt und nichts anderes, denn sonst wäre ja alles eine Primzahl.

Danke im Voraus.

...zur Frage

Haskell Funktion Frage?

Wenn man eine Funktion erstellen soll, bei der die Funktion zwei Werte nimmt und prüft, ob ein Wert durch den anderen teilbar ist, wie schreibt man das in Haskell als Code?

nehmen wir an:

isDivisible -> Integer -> Integer -> Bool

Wie schaut dann der Rest aus? So?

isDivisible x % y == 0 = true else false

y % x == 0 = true else false?? Das klingt so bescheuert aber ich weiß sonst nicht wie es aussehen sollte! Kann mir da wer weiterhelfen?

Zusätzlich müsste ich dann auch eine Funktion schreiben, die so aussieht:

isPrime -> Integer -> Bool

welches eine Zahl nimmt und ausgibt ob diese eine Primzahl ist oder nicht, dafür soll ich die vorherige Funktion benutzen, jedoch komm ich da eben nicht weiter. Und bei der hier bin ich mir auch nicht sicher, wie würde da der Code aussehen?

...zur Frage

Java: Wie kann ich bei einer Integer-Scanner-Eingabe whitespaces verbieten?

Hallo,

ich habe ein Primzahlberechnungs-programm geschrieben, bei der man eine Zahl eingibt und es sagen soll, ob es eine Primzahl ist. jedoch möchte bei eingaben wie "3 4 23 3" oder " 23 4 1" bei der whitespaces enthalten sind "ungültige Eingabe" angezeigt bekommen. Haben Sie eine Idee wie wie man prüft, ob die Integer-Eingabe whitespaces enthält?

Code:

import java.util.Scanner;

public class Primzahl {
        public static void main(String[] args)
        {
                System.out.println("Gib ne Zahl");
                Scanner scanner = new Scanner(System.in);
                Integer Zahl = scanner.nextInt();

                for (int i = 2; i < Zahl; i++)
                {
                        if (Zahl % i == 0)
                        {
                                    System.out.println(Zahl + " ist keine Primzahl");
                                    break;
                            }
                            else
                            {
                                    System.out.println(Zahl + " ist eine Primzahl");
                                    break;
                            }
                    }
            }
}

...zur Frage

Sieb des Eratosthenes in Golang?

Hallo,

mein Informatik-Lehrer hat uns eine Aufgabe gegeben, die wie folgt heißt:

Funktionieren soll das Programm wie folgt: Es wird ein Array von booleschen Werten angelegt, indiziert von 2 bis zur benötigten Größe, alle Einträge werden mit true initialisert. Der Wert false an Stelle i soll bedeuten, dass Zahl i sicher keine Primzahl ist. Wir durchlaufen die Zahlen ab i=2 bis zum Maximalwert und machen jeweils folgendes: Wenn der Eintrag an der Stelle i den Wert true hat, dann ist i eine Primzahl und diese wird ausgegeben, und alle Vielfachen von i werden in der Tabelle mit false gekennzeichnet. Implementiere dieses Verfahren, das als Sieb des Eratosthenes bekannt ist.

Mein Code sieht bisher so aus:

package main

import "fmt"
import "math"

func main() {
  var MAX_ZAHL int
  fmt.Println("Geben Sie die Zahl an, bis zu dessen Grenze die Primzahlen ausgegeben werden sollen!")
  fmt.Scanln(&MAX_ZAHL)
  fmt.Println("Die Primzahlen werden bis zu einer Größe von ", MAX_ZAHL, "ausgegeben")
}

Wie Arrays funktionieren, weiß ich. Aber durch die momentane Situation bei mir konnte ich nicht viel nachholen (und da mein Lehrer uns eher ohne Hilfen ausstattet).

Den boolschen Wert verstehe ich ebenfalls nicht so ganz.

Könnte mir jemand bei dieser Aufgabe helfen?

Danke im Voraus.

...zur Frage

Java Unterprogramm Primzahl?

Hallo zusammen,

kann mir jemand dabei helfen, ein Java Unterprogramm zur Berechnung der Primzahl zu entwickeln ? Die Fragestellung lautet wie folgt:

a) Der Benutzer kann eine Zahl x > 1 eingeben. Ist die Zahl größer als 1 wird ausgeben, ob es sich bei der Zahl um eine Primzahl handelt oder nicht. Eine Zahl x ist KEINE Primzahl, wenn eine Zahl zwischen 2 und x–1 existiert durch die sich x ohne Rest teilen lässt. Je nachdem, ob x eine Primzahl ist wird genau folgender Text ausgegeben (x ist durch die eingegebene Zahl zu ersetzen):  x ist eine Primzahl  x ist keine Primzahl

In dem Programm sollen geschachtelte Schleifen benutzt werden.

...zur Frage

Java: Primzahlen Programm?

Hallo,

ich muss ein Programm schreiben ob die Zahl n eine Primzahl ist oder nicht. Wenn sie keine ist soll per System.out.println() ausgegeben werden, dass es keine ist. Wenn es eine ist, dann soll sie als Primzahl ausgegeben werden.

...zur Frage

"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++;

        }

    }

...zur Frage

Java Primzahl boolean?

Ich muss eine Klassenmethode schreiben istPrim(long zahl), die true für eine positive Primzahl zurückgibt und false, falls die Zahl nicht prim ist.

Die Verwendung von main(), println(), und Scanner() ist nicht erlaubt.

Das hier ist der Code, den ich geschrieben habe. Sieht der richtig aus? Wenn nicht, was kann ich hier verbessern?

  public static boolean istPrim(long zahl) {
    boolean primZahl = true;
    long moeglicherTeiler = 2L;
  
    while (moeglicherTeiler < zahl) { // Teiler muss kleiner sein als Zahl selbst
      if (n % moeglicherTeiler == 0) { // Teiler gefunden -> keine Primzahl
        primZahl = false;
      }
  
      moeglicherTeiler = moeglicherTeiler + 1; // Teiler hochzählen
    }
  
    return primZahl;
  }
}

...zur Frage

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

...zur Frage

Java Primzahlen bis 8 testen?

In Java. Ich möchte alle Zahlen bis 8 testen lassen ob Sie Primzahlen sind oder nicht

Per Scanner wird die 8 eingelesen:

Am Ende soll ausgegeben werden:

Zahl 1 ist keine Primzahl

Zahl 2 ist Primzahl

Zahl 3 ist keine Primzahl

...

Zahl 8 ist keine Primzahl

Wie kriegt man dies hin: Doppelte for-Schleife?

...zur Frage

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

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen