Primzahlen Berechnung + weitere Verarbeitung



  • Hallo alle zusammen.
    Ich bin neu in diesem Gebiet und brauch für mein Studium einiges an Hilfe -.-
    Wir bekommen jede Woche eine Art Hausaufgabe und müssen die bis zum nächsten mal abliefern. Falls wir nicht schaffen, dürfen wir den Kurs nächstes Semester wiederholen.
    Soweit so gut. Ich habe bis jetzt "fast" keine Probleme gehabt. Doch die jetzige Aufgabe bekomme ich nicht geregelt. Und nochmal zur Erinnerung, ich bin ein totaler NOOB. Wenn was erklärt wird, bitte ich um einzelne detaillierte schritte und Erklärungen.

    Ich wollte nicht in die bestehenden Themen rein schreiben, da ich ganz konkret nur meine Aufgabe behandeln möchte und diese (meiner Meinung) einzig Artig bis jetzt hier ist 😉

    So nun zu meiner Aufgabe. Hier der Aufgabentext:

    Primzahlen
    Schreiben Sie ein C++-Programm, das ermittelt, für welche Zahlen z = (2^p)-1 ( 2 hoch p ) -1 Primzahlen sind, wenn p selbst eine Primzahl ist
    Beispiel Für p = 2 ist (2^2) -1 = 3 eine Primzahl oder
    für p = 3 ist (2^3)-1 = 7 eine Primzahl,
    aber x =(2^11) -1 = 2047 ist keine Primzahl.

    Berechnen Sie zunächst die ersten 500 Primzahlen und speichern Sie diese in ein Array pr_feld ab. Nachdem alle 500 Primzahlen berechnet sind, sind diese formatiert je 10 in einer Zeile auf dem Bildschirm auszugeben.
    Ermitteln Sie anschließend diejenigen Primzahlen, für die die obige Aussage zutreffend ist.

    Welche und wie viel der ersten 500 Primzahlen erfüllen die obige Bedingung? Geben Sie diese auf dem Bildschirm aus.
    Wie viel Primzahlen müssen Sie erzeugen, damit darin 5 Primzahlen enthalten sind, welche die Bedingung Primzahl_x = (2 hoch Primzahl) -1 erfüllen ?

    So das war die Aufgabe.
    Ich habe es geschafft, dass die ersten 500 Primzahlen angezeigt werden und im Array gespeichert werden.
    Nun scheitere ich aber darin, dass wenn ich nun die Primzahlen in die Rechnung eingebe mein Speicher ab ca. > 29 voll ist und er mir nur noch falsche / negative werte ausgibt.

    Ich hoffe Ihr könnte helfen.
    Hier der bisherige Stand:

    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    
    int n, rechnung, intern; //Interne Zählvariable(Wird durch "prim" geteilt um ganzzahligen Rest zu eritteln)
    int pr_feld[500];
    int prim = 2; //Aktuelle Zahl die überprüft wird
    int grenze = 5000; //Obere Grenze für Primzahlsuche
    
    void main()
    {	
    	for(prim ; prim<grenze ; prim++) //Alle Zahlen von Anfangszähler bis zur Grenze überprüfen
        {
            for(intern=(prim-1) ; prim%intern ; intern--) //Schleife die so lange läuft, bis die Modulo-Operation 0 liefert
            {}
            if(intern == 1) //Wenn "prim" nur durch 1 den Rest 0 hat, dann ist "prim" eine Primzahl
            {
    			pr_feld[n++] = prim;
            }
        }
    	for (n=0; n<500; n++)
    	{	
    		printf("%ld\t",pr_feld[n]);
    	}
    
    	printf("Das waren alle Primzahlen bis zur 500ten Primzahl\n\n");
    	printf("Als naechstes werden alle Primzahlen berechnet,\nwelche die Bedingung (2^p)-1 erfuellen\n");
    	system ("pause");
    
    	for (n=0; n<15; n++) // Ab hier wollte ich testen, ob die Primzahlen wirklich berechnet werden können. Und ier komm ich auch nicht wirklich weiter
    	{	
    		rechnung = pow((long double)2,(long double)pr_feld[n])-1;
    		printf("%ld\t",rechnung);
    	}
    
    	system ("pause");
    }
    


  • Mach es dir doch einfach, das genaue Vorgehen ist im Text nicht beschrieben.
    Gehe in einer Schleife

    for(i=1;i<=11;++i)
    {
      val = (1<<i)-i; // 2[h]i[/h]-1
      if(val>(pr_feld[499])) // val ist größer als die größe gefundene Primzahl -> Abbruch
        break;
      if(IsPrime(val)) // Funktion auslagern
      {
        // juhu
      }
    }
    

    Alternativ kannst du immer die Liste durchsuchen, dies ist aber nicht notwendig.
    Übrigens: Es sind 4.

    Edit: Habe den letzten Satz überlesen, aber geh' einfach genau so ab i bis 31 weiter, bis die Anzahl der gefundenen Zahlen 5 erreicht.



  • Vicious Falcon schrieb:

    for(i=1;i<=11;++i)
    {
      val = (1<<i)-i; // 2[h]i[/h]-1
    
    ...
    

    Du setzt hier in die fragliche Formel: z = (2^p)-1 für p die Werte 1 - 11 bzw. gem. Deinem Nachtrag 1 - 31 ein. Nach der Aufgabenstellung sollen aber nur (die vorher gefundenen) Primzahlen für p eingesetzt werden.


  • Mod

    kingbizlip4u schrieb:

    Nun scheitere ich aber darin, dass wenn ich nun die Primzahlen in die Rechnung eingebe mein Speicher ab ca. > 29 voll ist und er mir nur noch falsche / negative werte ausgibt.

    Du bekommst vermutlich Überläufe oder es liegt an deinem fehlerhaften printf. Aber das ist alles gar kein Problem, guck mal auf die Werte von deinen Primzahlen und die Werte die du bei 2^p-1 herausbekommst: Die größte Primzahl ist 3571, doch schon die sechste Zahl bei 2^p-1 ist 8191. Bau einfach noch eine Bedingung ein, um nach Überschreiten der letzten Primzahl abzubrechen.

    Und Codestil! 😮 Bekommt man so etwas heutzutage an der Uni beigebracht? Mit so einem Stil ist es nur eine Frage der Zeit bis du schwer zu findende Bugs einbaust. Globale Variablen, mit magischen Werten initialisiert. Weitere magische Zahlen im ganzen Programm verteilt. Compilerwarnungen ohne Ende (viele davon berechtigt). Teilweise Kommentare die das offensichtliche zum Ausdruck bringen (ich gucke hier die Zeile 14 an).



  • Belli schrieb:

    Nach der Aufgabenstellung sollen aber nur (die vorher gefundenen) Primzahlen für p eingesetzt werden.

    Ja, du hast Recht, das Prinzip kann dennoch das Gleiche bleiben.
    (1<<p)-1 ist bei 32-Bit-Zahlen bis p gleich einschließlich 31 definiert.



  • Klar, man kommt aber nicht weit genug. Der mögliche Maximalwert von 31 reicht bei weitem nicht aus.



  • Belli schrieb:

    Klar, man kommt aber nicht weit genug. Der mögliche Maximalwert von 31 reicht bei weitem nicht aus.

    Edit: Ich glaube, das war Blödsinn ...



  • kingbizlip4u schrieb:

    ...
    
    	for (n=0; n<15; n++) // Ab hier wollte ich testen, ob die Primzahlen wirklich berechnet werden können. Und ier komm ich auch nicht wirklich weiter
    	{	
    		rechnung = pow((long double)2,(long double)pr_feld[n])-1;
    		printf("%ld\t",rechnung);
    	}
    
    ...
    

    Wenn Du in dieser Schleife überprüfst, ob rechnung eine Primzahl ist, und nach der fünften gefundenen Primzahl die Schleife verlässt (was, so wie ich es verstanden habe, der Aufgabenstellung entspricht), bist Du fertig, bevor der Überlauf eintritt.



  • Man kann den letzen Punkt aber auch als eigene Aufgabenstellung betrachten, daher eine seperate Schleife:

    for(;i<32;++i) // i ist noch gespeichert
        if(IsPrime(i) && IsPrime((1<<i)-1))
        { // wenn 5 gefunden, Abbruch
        }
    

    Im Grunde genommen ist es eigentlich egal, da die Bedingung IsPrime((1<<i)-1)) nur erfüllt ist, wenn i selber eine Primzahl ist.



  • Hallo,
    so ganz habe ich es immer noch nicht verstanden, leider.
    Vielleicht habe ich die Aufgabenstellung auch falsch verstanden.
    Ich dachte ich muss jede Primzahl die ich raus bekomme prüfen ob sie die Bedingung (2^p)-1 = primzahl erfüllt.

    @SeppJ,
    wegen Codestil. Wir haben die Vorlesung bis jetzt nur 4 mal gehabt. In der Vorlesung wurde etwas zur Geschichte erzählt, wie so ein C Programm aufgebaut ist (welche Grundlegenden Befehle es gibt), der Aufbau, Algorithmen, Syntax und letzte Stunde noch arrays. Dazu kommt noch ein Technischer Teil mit Allgemein Informationen, Bits und Bytes, Codierung / Decodierung, Zahlensysteme (Dual-, Oktal-, Dezimal-, Hexadezimalsysteme), 1er und 2er-Komplement.
    Das ist zusammengefasst das ganze Input bis jetzt (der letzetn 4 bzw. 8 Vorlesungsblöcke) + Die Aufgaben, die wir bis zum nächsten mal machen sollen.

    Wo her soll ich den auch wissen wie man bitte ein Code "richtig" und/oder schön schreibe?! Ich finde einfach, dass wir zu wenig Informationen bekommen haben und wir einfach ins kalte Wasser geworfen werden. Deshalb schreib ich ja das Forum an, damit ich Hilfe und Verbesserungsvorschläge bekomme.
    PS: Die Globalen Variablen funktionieren bei mir nicht, wenn Sie in der Main() stehen.
    PSS: Compilerwarnugen sind laut unserem Dozent nicht wichtig, sollten aber mal angeschaut werden Oo (i know. Tolle aussage -.- )

    Ich habe es bis jetzt leider auch nicht durch eure Hilfe hin bekommen, den letzten Teil zu berechnen. Ich glaube einfach, dass ich die Aufgabenstellung falsch verstanden habe. Ich gehe davon aus, dass ich ALLE Primzahlen, die ich bis jetzt gefunden habe in die Rechnung (2^p)-1 einsetzten soll und dann schauen soll, ob das Ergebnis wieder eine Primzahl ist.
    Falls ich falsch liege, was ich so langsam das Gefühl bekomme, dann werde ich Anfang nächste Woche nochmal jemanden im höheren Semester befragen, wie die Fragestellung genau gemeint ist.

    LG
    kingbizlip4u



  • trifft man mit mersenne primzahlen alle? ich denke nicht! naja aber wenn ihr eh schon compiler warnungen ignorieren dürft, kommts auf diese kleine ungenauigkeit auch nicht mehr an 🤡



  • Im Prinzip müsste die Schleife so aufgebaut sein, als ob du alle 500 gefundenen Primzahlen prüfen willst. Nach dem fünften Fund (213-1 = 8191) kann jedoch schon abgebrochen werden.
    Eine Rechnung von 23571-1 und die Auswertung, ob das Ergebnis eine Primzahl ist, kann nach wenigen Vorlesungen nicht gelöst werden (Stichwort BigInt).

    Und noch etwas: Warnungen des Compilers sind nicht "böse", sondern ein ernst zu nehmender Ratschlag, sich die entsprechenden Codestellen noch einmal anzusehen und diese zu ändern.



  • Hi,
    mir ist klar, dass wenn der Compiler einer Warnung ausgibt, diese auch berechtigt ist und man versuchen sollte das zu beheben. Ich denke aber auch, dass ich mit dem derzeitigen Stand nur weniger Warnung beheben kann.

    Um wieder zu meinem zweiten Teil zu kommen. Ich habe meine rechnung (2^p)-1 geschrieben und möchte die nun vergleichen, ob die Lösung im array vorhanden ist. Ich weis aber (wieder mal) nicht, wie ich das genau sagen soll.

    for (n=0; n<10; n++)
    	{	
    		rechnung = pow((double)2,(double)pr_feld[n])-1;
    		if (rechnung < 5000 && rechnung == pr_feld[n]) // hier wollte ich die Lösung der Rechnung prüfen. Gibt es die Zahl schon im Array, wenn ja soll er die Lösung zeigen. 
    		{
    			printf("%ld\n", rechnung);
    		}
    	}
    

    Ganz blöd gesagt, geht net ^^ Ich denke ich muss das rechnung == pr_feld[n] irgendwie anders lösen. wenn ich rechnung == pr_feld[1] || rechnung == pr_feld[3] etc. mache, dann gibt er mir das richtige aus. Das kann ich aber net machen, da ich ihm ja die Lösung "irgendwie" vorgebe.



  • Hallo,
    ich wollte nur nochmal mein Feedback abgeben. Ich habe das Programm nun fertig.
    Der Anfang war schon richtig.
    Der zweiten Teil hab eich nun auch hin bekommen.

    Ich bedanke mich schon mal an allen die mir geholfen haben.
    Ich werde mich in Zukunft gerne wieder bei euch melden, wenn ich Probleme habe.

    Lg
    kingbizlip4u



  • Hallo,

    also die ersten 500 Primzahlen, kein Ding. Aber wer hat eine Idee wie das Kriterium in der Aufgabe kontrolliert werden soll. Ich kenn das nur so, dass Float-Zahlen ziemlich ungenau sind, ausserdem lassen die sich nicht Modulo rechnen. Also, wenn jemand eine Lösung hat, schreib bitte, interessiert mich wirklich. Nur mal so hänge ich meinen Code mal unten an, hab wphl keine Kommentare drangeschrieben:

    #include <stdio.h>
    #include <stdlib.h>
    
    #define ARRAYSIZE   500
    #define TRUE        1
    #define FALSE       0
    
    int isprim(unsigned long int);
    
    int main()
    {
       int PrimCount = 0;
       int *pr_feld;
       unsigned long int TestVal = 2;
       unsigned long int i;
    
       pr_feld = malloc(sizeof (int) * ARRAYSIZE);
    
       while (PrimCount < ARRAYSIZE)
       {
    	   if (isprim(TestVal))
    	   {
    		   pr_feld[PrimCount] = TestVal;
    		   PrimCount++;
    	   }
    	   TestVal++;
       }
    
       for(i=0; i< ARRAYSIZE; i++)
       {
    	   printf("%8d", pr_feld[i]);
    	   if(!((i+1) % 10))
    			   printf("\n");
       }
    
       return 0;
    }
    
    int isprim(unsigned long int Val)
    {
    	int i;
    	int RetVal = TRUE;
    
    	for(i=2; i < Val; i++)
    	{
    		if (!(Val % i))
    		{
    			RetVal = FALSE;
    			i      = Val;
    		}
    	}
    	return RetVal;
    }
    

    Danke für die Antworten.



  • Wie kommst du auf floats? Weder in deinem Code noch in den Vorherigen wurden sie verwendet.
    Wenn du dich nur für die Zahlen interessierst, nicht jedoch die Aufgabenstellung beachten willst bzw. musst, gibt es eine sehr einfache Lösung.
    Gesucht sind die Zahlen, bei denen (2p)-1 eine Primzahl ist, wenn p ebenfalls eine Primzahl ist. Wenn man sich nun auf den 32 Bitbreich konzentriert, kann man schreiben:

    for(unsigned int i=2;i<32;++i)
    		if(IsPrime(i) && IsPrime((1<<i)-1))
    			printf("%d\n",(1<<i)-1);
    

    Deine Primzahlberechnung ist übrigens fehlerhaft, 1 ist keine Primzahl 🙂 .



  • Ich habe die Aufgabe so gelöst. Ich denke so wollte der Prof das auch haben. Spätestens am Donnerstag weiß ich, ob die Aufgabe richtig ist oder nicht 😛

    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    
    int n, k ,i; //Interne Zählvariablen
    int Primzahl_x, pr_feld[1200]; 
    int prim = 2; //Aktuelle Zahl die überprüft wird
    int grenze = 10000; //Obere Grenze für Primzahlsuche
    
    //ich weis, variable Global = BÖSE! Aber wenn ich sie in die Main ziehe kommt Fehler -.-
    
    void main()
    {	
    	for(prim ; prim<grenze ; prim++) //Alle Zahlen von Anfangszähler bis zur Grenze überprüfen
        {
            for(i=(prim-1) ; prim%i ; i--) //Schleife die so lange läuft, bis die Modulo-Operation 0 liefert
            {}
            if(i == 1) //Wenn "prim" nur durch 1 den Rest 0 hat, dann ist "prim" eine Primzahl
            {
    			pr_feld[n++] = prim;
            }
        }
    	for (n=0; n<500; n++) //Es werden nur die ersten 500 Primzahlen ausgegeben
    	{	
    		printf("%d\t",pr_feld[n]);
    	}
    
    	printf("Das waren alle Primzahlen bis zur 500ten Primzahl\n\n");
    	printf("-------------------------------------------------\n\n");
    	printf("Als naechstes werden alle Primzahlen berechnet,\nwelche die Bedingung (2^p)-1 erfuellen:\n\n");
    
    	k=0;
    	for (n=0; n<500; n++)
    	{	
    		Primzahl_x = pow((double)2,(double)pr_feld[n])-1; //Bedinung wird überprüft. Falls ergebnis in pr_feld existiert, wird die Primzahl ausgegeben.
    		for (i=0; i<500; i++)
    		{
    			if (Primzahl_x == pr_feld[i]) // Primzahlberechnung wird verglichen mit dem vorhandenen Arrays.
    			{
    				printf("%d\t", pr_feld[n]);
    				k++;
    			}
    		}
    	}
    	printf("\n\nAnzahl der Primzahlen: %d", k);
    	printf("\n\n-------------------------------------------------\n\n");
    	printf("Man muss"); 	
    
    	Primzahl_x = pow((double)2,(double)pr_feld[5])-1; //Welche nächste Primzahl wird benötigt, damit darin 5 Primzahlen hintereinander sind. 
    	for (i=0; i<1200; i++)
    	{
    		pr_feld[i];
    		if (Primzahl_x == pr_feld[i])
    		{
    			printf(" %d ", i+1);
    		}
    	}
    	printf(" Primzahl erzeugen, damit darin 5 Primzahlen enthalten sind.\n");
    	printf("\n-------------------------------------------------\n\n");
    	system ("pause");
    }
    

  • Mod

    Wenn das eine Übungsaufgabe für ein Hochschule ist, kann ich dir versichern, dass dies unter dem Erwartungshorizont deines Profs ist. Selbst in einer normalen Schule wäre ich als Lehrer enttäuscht, wenn dies die beste Primzahlsuche ist, auf die ein Schüler selbstständig kommt. Und bei so langer Zeit die Aufgabe zu lösen, hätte man auch ein wenig Recherchearbeit erwarten können, so dass man selbst ohne eigenes denken einen guten Algorithmus findet.

    Und auch programmiertechnisch ist dein Programm enttäuschend, dein Kommentar zu globalen Variablen macht deutlich, dass dir dies auch teilweise bewusst ist. Dazu kommt Zeile 14 bei der du zeigst, dass du for nicht 100% verstanden hast, Zeile 52, wo nicht passiert. Überall fliegen magische Zahlen rum.

    Ob's überhaupt richtig ist, habe ich jetzt nicht geprüft.



  • @leyden und @kingbizlip4u

    Wenn ihr wissen wollt ob die Zahl N eine Primzahl ist braucht ihr nicht bis N-1 sondern nur bis sqrt(N)+1 suchen.
    Bsp:
    210 : 2 = 105 -> 210 : 105 = 2
    210 : 3 = 70
    210 : 5 = 42
    210 : 7 = 30
    210 : 10 = 21 -> 210 : 21 = 10
    210 : 11 = 19,..
    210 : 13 = 17,5
    210 : 14 = 15 -> 210 : 14 = 15
    210 : 15 = 14 -> hatten wir schon

    Das wären dann in diesem Fall 14 statt 209 Vergleiche.
    Wenn Ihr dann nur noch durch alle ungeraden Zahlen teilt bleiben noch 7 Vergleiche übrig.


  • Mod

    Noch besser: Man kennt ja schon die kleineren Primzahlen. Dies sind die einzigen Zahlen die man testen muss.


Log in to reply