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?

6 Antworten

bormolino

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

Computer, programmieren

13.06.2017, 22:47

Man prüft ganz einfach ob die übergebene Zahl nur durch sich selbst und durch 1 teilbar ist. Das bekommst du sicher ganz einfach hin.

Hier nochmal eine optimierte Version des Primzahltests als Funktion in C:

#include <math.h>

typedef enum { false, true } bool;

bool isPrime(long n) {
    if(n == 1)
        return false;

    else if(n == 2)
        return true;

    else {
        long i, r = (long) sqrt(n);

        for(i = 2; i <= r && n % i != 0; ++i);

        return (r == i - 1) ? true : false;
    }
}

Grüße - bormolino

Woher ich das weiß:Studium / Ausbildung – Studium Informatik und Hobby seit einigen Jahren

PeterKremsner

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

Computer

13.06.2017, 21:43

Du kannst dir im Prinzip alle Primzahlen bis zu deiner Zahl bilden.

Die Zahlen 2 und 3 schreibst du einfach in den Code rein.

Dann schreibst du folgendes:


int i;
char isPrime;
for(i = 5; i <= gesuchteZahl; i = i+2)
{
   isPrime = 1;
   for(alle gefundenen Primzahlen, außer 2)
   {
      if((i % Primzahl) == 0)
      {
         //i ist keine Primzahl
         isPrime = 0;
         break;
      }
   }
   if(isPrime)
   {
      i zu den gefunden Primzahlen dazu geben
   }
}

Wenn am Ende, diese Algorithmus deine Zahl bei den gefundenen Primzahlen steht, sprich am letzten Platz deines Arrays ist deine Zahl eine Primzahlen.

Basieren tut der Algorithmus auf der mindestdistanz aller von aller Primzahlen >= 3 diese ist nämlich mindestens 2 (vielleicht auch größer, aber das ist eine einfache untere Schranke), darum inkrementiert man immer um 2.

Das suchen ob es sich bei i nun um einen Primzahl handelt, basiert auf der Primfaktorzerlegung, jede Zahl ist nämlich durch eine Multiplikation von Primzahlen darstellbar und damit auch durch mindestens eine kleinere Primzahl ganzzeilig Teilbar.

PWolff

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

Computer

13.06.2017, 22:57

AusgegebeneZahl ist schon das Ergebnis einer Division; du prüfst später noch mal, ob der Rest einer Division 0 ist.

Wenn eine Zahl n durch eine andere Zahl k teilbar ist, hat das nichts damit zu tun, ob n auch durch (n-k) teilbar ist.

(Übrigens reicht es, zu prüfen, bis Quotient < Divisor)

Woher ich das weiß:Berufserfahrung – Software-Entwickler

ichweisnix

04.08.2017, 20:58

1. ) ganz einfach AusgabeZahl % counter ist bei counter = 1 immer wahr.

2.) sie sollten die Funktion verlassen, wenn sie einen Teiler gefunden haben.

3.) Ihre Schleife sollte von 2 beginnen und so lange gehen bis das qudrat größer als die eingabezahl ist.

 
for( int i = 2 ; i*i <= eingabezahl ; i++ ) 
  if( eingabezahl % i == 0 ) 
  { 
    printf("Zahl %i ist durch %i teilbar.",eingabezahl,i);
    return 0;
  }

printf("Zahl %i ist prim.",eingabezahl);

jadaniil

01.05.2020, 21:39

wie kommst du bei dem for auf "i*i <= eingabezahl", wieso bitte i mal i????(schon klar wegen Punkt 3)"bis Quadrat größer als Eingabezahl", aber wie kommst du bitte darauf?)
Und würde das zweite Printf bei einer hohen Primzahl nicht ewig oft immer wieder drankommen und unnötig oft in den Compiler ausgegeben?

KirmesRuf6

01.08.2017, 02:27

Du könntest es umständlich machen, alle Zahlen durchgehen, sie teilen, und darauf achten, ob Nachkommazahlen herauskommen..

/ Primzahl.c /

include include

main()

{ int zahl=16; //Zum Testen

int counter = 1; //Counter für die Schleife

int rest = 1; //Variable für den Rest (Modulo)

while (counter < (zahl-1)) //Solange counter < 15 (Also von 1 bis 14)

rest = zahl%(zahl-counter); //(16/Alle kleineren natürlichen Zahlen bis auf 1)

if (rest=0) //Ist die Zahl Restfrei durch eine kleinere natürliche Zahl teilbar, ist die Zahl keine Primzahl;

{ printf("Diese Zahl ist keine Primzahl"); }

counter++; //Counter wird um 1 erhöht und die Schleife beginnt erneut }

system("pause"); //Damit das Programm sich nach beendigung seiner Aufgabe nicht gleivh selbst auslöscht }

Das Programm funktioniert nicht. Deswegen meine Frage: Wo liegt der Fehler?

Danke im Voraus ;)

...zur Frage

Wir sollen im Unterricht eine Schleife erstellen, die alle Primzahlen bis 100 ausgibt, jedoch sitzen wir seid mehreren Stunden dran und kriegen es nicht hin?

Wir sollen das ganze in While schleifen schreiben, doch haben keinen blassen Schimmer wie dieses gehen soll.

Das haben wir bisher.

public class Main {
    public static void main(String[] args) {
        int limit = 100;
        int zahl;                   //überprüfen der zahl
        int counter= 2;
        boolean prim;           //Hilfsvariable ob die aktuelle zahl eine Primzahl ist

        for (zahl = 2; zahl <= limit; zahl++) {
            prim = true;
            while(counter < Math.sqrt(zahl) + 1) {
                counter++;

                if (zahl % counter == 0) {
                    prim = false;

                } else if (prim) {
                    System.out.println(zahl + " ");
                }
            }
        }
    }
}

...zur Frage

wörter umdrehen und palindrome finden in c?

heyho :) ich wollte testen ob das wort, was ich eingegeben habe auch ein palindrom ist, also umgekehrt genau dasselbe wort ergibt. Nun versuche ich nach dem letzten kommentar zu vergleichen also ob die werte gleich sind, weil so wäre es ein palindrom. Jedoch finde ich meinen fehler nicht und wollte mal fragen ob einer von euch ihn findet :) LG Alina

include
include 
int main(){
//einlesen
  printf("Geben Sie die Länge des Strings an");
  int a;
  scanf("%i", &a);
  char text[a];
  printf("Text eingeben:\n");
  int i;
  for (i=0;i<a;i++){
    scanf("%c", &text[i]);
  }
  //umgekehrt ausgeben
  int c;
  c=a;
  while (c!=0){
    printf("%c", text[c]);
    c--;
  }
  //Palindrom oder nicht 
  int count=0;
  i=1;
  int d;
  d=a; //5
  while (text[i]==text[d]){
    count ++;
    i++;
    d--;
  }
  if(count == a){
    printf("palindrom");
  }
  return 0;
}

...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

Primzahlen berechnen in Java?

Hallo,

ich versuche derzeit ein Programm zu schreiben, das mir Primzahlen errechnet. Es lässt sich auch fehlerfrei kompilieren, aber Primzahlen kommen keine raus. Anscheinend wird das Ergebnis automatisch abgerundet. Ich wäre sehr froh, wenn ihr mir den Fehler (oder die Fehler :-) ) aufzeigen könntet oder mir eine bessere Methode schreiben würdet.

public class Primzahlen {
 public static void main (String[] args) {
  int Zahl = 13;
  double d1;

  for(int i = 2; i < Zahl; i++) {
   d1 = Zahl/i;
   int i1 = (int) d1;
   System.out.println(d1-i1 + "  Ergebnis " + Zahl+ "/" + i + ": " + d1 + "  Zahl: " + Zahl + "  Divisor:  " + i);

   if ((d1 - i1) == 0.0) {
    System.out.println(Zahl + " ist keine Primzahl, sie ist durch " + i + " teilbar.");
    break;
   } else {
    if ((i+1) == Zahl) {
     System.out.println(Zahl + " ist eine Primzahl");
     break;
    }
   }
  }
 }
}

Kompilierte Version und Quellcode: http://db.tt/nRNKnOQ2

...zur Frage

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 ;)

...zur Frage

C: Berechnung Summe negativer Zahlen?

Hi,

die Funktion soll die Summe aller negativen, ungeraden, ganzen Zahlen, die >= einer Zahl x < 0 sind, berechnen.

Beispiel:

Mein Teilcode:

int i;
int n;

void Summe(int k) {
  if (k > 0) {
    printf("Error\");
  }
  else {
    for (i = 0; i <= k; i++) {
      n = n + 1;
    }
  }
}

Ich denke, der Fehler liegt in der if-Schleife. Wenn ich -8 eingebe, kommt 0 raus.

...zur Frage

Wie kann man in C ohne die string.h-Bibliothek prüfen, ob die Eingabe einem Palindrom entspricht?

Hey,

wie kann man in C ohne die string.h-Bibliothek prüfen, ob die Eingabe einem Palindrom entspricht?

Hier der Code:

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

#define LAENGE 80

void laenge(char , int , int);

int palindrom();

int main()
{
  char string[LAENGE] = { 1 };
  int count = 0, kleinb = 90, palindrom = 0;

  printf("Vor dem Dienstag kommt der Montag.\n");
  printf("Gebe deinen Text bitte ein : \n");
  gets(string);
  laenge(string, &count, kleinb);

  printf("Buchstaben in gross: %s\n", string);
  printf("Die Stringlaenge: %d\n", count);

  return 0;
}

void laenge(char string [], int count, int kleinb)
{
  for (int i = 0; i < LAENGE; i++) {
    if (string[i] != 0) {
      (count)++;
    }

    if (string[i] > kleinb) {
      string[i] = string[i] - 32;
    }
  }
}

int palindrom()
{
}

...zur Frage

Funktion für die Primfaktorzerlegung?

Diese Funktion soll die Primfaktoren einer Zahl berechnen und in der main funktion ausgeben. Tut sie auch. Das ist alles kein Problem. Ich verstehe nur nicht, was über dem Printf passiert. Was bedeutet das und warum wird das gemacht? Wenn ich das weg mache gibt mir der Debugger 2*2*2*2*2*2*2...........

Aber warum?

Ich hoffe, man kann mir helfen. Ich bin noch ein Neuling und versuche grade zu lernen. Danke

int primfakt(int zahl) { //Funktion für die Primfaktorzerlegung

int i = 2;

while (i <= zahl) // while schleife bis zur Zahl

{

if (zahl % i == 0) //Wenn zahl restlos Teilbar -> Ausgeben

{

zahl = zahl / i;

printf("%i*", i); //wird in der Main Funktion ausgegeben

}

else

i++; // ansonsten erhöhe i um 1

}

...zur Frage

C: Dezimal in Binär umrechnen?

Hallo Leute,

ich muss ein Programm schreiben, welches eine Dezimalzahl in eine binäre Zahl umwandelt. Ich habe es schon programmiert, aber wenn ich 2 eingebe, kommt 10 heraus. Das stimmt auch, aber gehören davor noch zwei Nullen, sodass 0010 da steht? Wenn ja, wie geht das?

Danke für die Hilfe.

Hier mein Code:

int main(void)
{
  int zahl = 0, dezimal = 0, rest = 0, ergebnis = 0, faktor = 1;
  char wiederholen = 0;

  printf("\nDieses Programm wandelt Dezimalzahlen in Dualzahlen um.\n");
  printf("--------------------------------------------------------------");

  printf("\nZahl eingeben: ");
  scanf("%d", &dezimal);

  zahl = dezimal;

  while (dezimal != 0) {
    rest = dezimal % 2;
    dezimal = dezimal / 2;
    ergebnis = ergebnis + (rest * faktor);
    faktor *= 10;
  }

  printf("Binaer : %d \n", ergebnis);

  printf("\nWollen Sie das Programm wiederholen (j/n)?");
  wiederholen = getche();

  if ((wiederholen == 'j') || (wiederholen == 'J')) {
    return main();
  }
  else return EXIT_SUCCESS;
}

...zur Frage

scanf wird ignoriert?

#include <stdio.h>

int main()
{
  int a;
  int error;
  printf("Geben sie eine Zahl ein: \n");

  do {
    error = scanf("%d", &a);
    printf("error: %d\tZahl:%d\n", error, a);
  }
  while (error == 0);

  return 0;
}

Die Schleife soll solange durchlaufen werden, bis eine Zahl eingegeben wurde.

Stattdessen wird scanf einfach nach dem ersten Durchlauf nicht mehr aufgerufen und man landet in einer Endlosschleife. Warum?

...zur Frage

C Ziffernsumme mit while Schleife?

Könnte mir wer helfen was da falsch ist? Sobald ich 10 oder mehr Zeichen eingebe stimmt es nicht/rechnet komplett falsche Werte aus.

#include <stdio.h>

int main()

{

int number;

int digitSum = 0;

int i;

printf("Bitte eine ganze Zahl eingeben: ");

scanf("%d", &number);

while(number != 0)

{

digitSum = digitSum + number % 10;

number = number / 10;

}

printf("Ziffernsumme: %d", digitSum);

return 0;

}

...zur Frage

C-Programmierung -> Zahlen verdoppeln mit while

Aktuell habe ich folgende Kontruktion:

include<stdio.h>

int main()

{

int i=1;

while(i <= 100)

{ printf("Zahl %d\n", i);

**i++;**

}

getch();

return 0; }

Meine Zahlen werden also aktuell solange um 1 erhöht mis 100 erreicht ist.

Mein Problem liegt bei dem ** i++**.

Wenn ich beispielsweise i+2 stattdessen eingebe, kommt unendlich of nur die 1 in der Konsole, benso mit * oder ähnlichem, nur i++ funktioniert, was mache ich falsch?

...zur Frage

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");
    }
}

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen