C++ Primfaktorzerlegung nur bis 9-stellige Zahlen

[7Jonas7]

Guten Tag!

Ich habe ein Programm zur Primfaktorzerlegung geschrieben und es funktioniert nur teilweise, vielleicht kann mir jemand weiterhelfen.

Das Programm funktioniert für jede Zahl unter 2147483647 (es ist eine 10-stellige Primzahl), wenn man eine Zahl die größer ist eingibt, wird nur diese Primzahl ausgegeben. Mir reichen 9-stellige Zahlen bzw. ein paar 10-stellige Zahlen noch nicht, deshalb muss das Programm auch größere Zahlen zerlegen können.

Ich habe bereits versucht, int mit long int bzw. long long und auch unsigned int zu ersetzen für mehr Speicherplatz, jedoch bringt das nichts.

Es ist eins meiner ersten Programme und ich habe noch nicht viel mit C++ programmiert, darum wäre es nett, wenn mir jemand helfen könnte.

#include <iostream>

using namespace std;                                                   //benötigte Befehle einfügen

int main()                                                                      // Anfang
{
    int zahl = 0;                                                              // Variablen einfügen
    int p = 2;


    while (zahl < 2)                                                        // Zahl muss größer als 2 sein für die Primfaktorzerlegung
    {
        cout << "Bitte geben Sie eine Zahl größer als 1 ein: ";
        cin >>  zahl;                                                        // Eingabe der zahl
    }


    while (p <= zahl)                                                    // Anfang Primfaktorzerlegung
    {
        if (zahl % p == 0)                                               // Prüfung auf Teilbarkeit
        {
            cout << p << "*";                                          // Ausgabe der Primzahl
            zahl /= p;                                                       // Zahl wird durch die Primzahl geteilt
        }
        else
            p++;
    }

    return 0;
}

 

[madmax2010]

https://de.wikipedia.org/wiki/Integer_(Datentyp)#Maximaler_Wertebereich

Klingt irgendwie nach einer Hausaufgabe

 

[tollertyp]

Die Logik stimmt auch sicher nicht.
Beispiel 8: 2*2*2
Bei dir würde 2*4 rauskommen

 

[wayne_757]

Klingt irgendwie nach einer Hausaufgabe

Ist auch kein Problem. Er will ja keine Lösung für die Aufgabenstellung sondern hat eine Frage zu einem Subproblem

 

[michi.o]

Programmierst Du auf einem PC oder einem anderen Gerät wie z.B. Raspberry Pi? (verschiedene Compiler interpretieren die Länge von Datentypen anders)
Wenn ich Deine int durch long long ersetze und mit Visual Studio unter Windows baue funktioniert Dein Programm. Vielleicht hast Du beim Ersetzen was übersehen.

    int main()    // Anfang
    {

        long long zahl = 0;     // Variablen einfügen
        long long p = 2;

 

[Sahit]

@madmax2010 finde ich hier ja auch nicht schlimm er hat sich Gedanken gemacht und was auf die Beine gestellt was soweit erstmal funktioniert dann kann man sich ruhig mal Hilfe holen.

 

[madmax2010]

@Sahit @wayne_757 Volle Zustimmung. Bin nur etwas irritiert, entweder der Lehrer hat vor, dass seine SuS hierdurch Datentypen verstehen, was reichlich seltsam wäre, oder er hat Datentypen nur sehr flüchtig behandelt.
Ich habe oben erstmal nur zu Wikipedia gelinkt, weil da halt auch schon alles steht, was um das Problem zu lösen nötig ist

 

[7Jonas7]

Danke für die schnellen Antworten ^^

@madmax2010 es ist mehr freiwillig als richtige Hausaufgabe.

@tollertyp bei mir kommt 2*2*2 raus, wenn ich 8 eingebe.

@michi.o Ich programmiere am PC. Ryzen5 3600 + Nvidia rtx 3070 + 24GB RAM, falls das irgendwie hilft. Ich arbeite auch auf Windows und mit Visual Studio und bei mir funktioniert es nicht mit long long, habe ich schon mehrmals probiert. Ich schreibe gleich den ganzen Code in ein neues Projekt und versuche es erneut.

 

[frazzlerunning]

bei mir kommt 2*2*2 raus, wenn ich 8 eingebe.

bei dem cout?

cout << p << "*";

Da sollte 2*2*2* rauskommen; kann es aber nicht, bei dem restlichen code.

 

[tollertyp]

Das kann halt kaum stimmen:

Das führt dazu, dass jeder Primfaktor nur einmal "erkannt" wird.

Die Position des Ausdrucks "p++;" ist halt zweifelhaft.

 

[michi.o]

@7Jonas7
Passt, mir gings um den CPU Typ. Ryzen ist eine x86-64 CPU. Beim ARM CPUs hatte ich schon Probleme mit unterschiedlichen Längen.
Wenn Du den Compiler von Visual Studio nutzt, dann sind int und long identisch. Erst long long gibt eine 64-bit Zahl. Die Zahlenbereiche sind hier aufgelistet:
https://docs.microsoft.com/de-de/cpp/cpp/data-type-ranges?view=msvc-160

 

[S.Kara]

Du beötigst ein 128 Bit Integer, was es im Standard allerdings (leider) nicht gibt. Da musst du selbst Hand anlegen oder eine Lösung aus dem Internet suchen.

https://www.boost.org/doc/libs/1_62...ml/boost_multiprecision/tut/ints/cpp_int.html

Übrigens reicht es bis zur Wurzel zu vergleichen:
while (p <= sqrt(zahl))

 

[deveth0]

Du kannst das auch noch etwas optimieren, indem du p immer um 2 erhöhst (es gibt nur eine gerade Primzahl), damit halbierst du schonmal die Schritte.

 

[7Jonas7]

@tollertyp die Klammern sind unnötig, da gebe ich dir Recht.

@S.Kara ist das möglich mit C++ und Visual Studio oder muss ich dafür etwas anderes benutzen?

@deveth0 danke ^^

 

[frazzlerunning]

p immer um 2 erhöhst

nicht immer

 

[tollertyp]

@7Jonas7: Unnötig und falsch ist nicht dasselbe... Unnötig würde heißen, dass es dennoch korrekt funktioniert. Das tut es aber nicht.
Oder du machst einfach das p++; in die Klammern.

 

[frazzlerunning]

while (p <= zahl)                          // 2<=8? dann mach ich mal.
    {
        if (zahl % p == 0)                  // 2%8 == 0? Ja
        {   cout << p << "*";              // Ausgabe "2*"
            zahl /= p;                           // zahl dann 4
        }
        else   {  }
        p++;                                    // p wird 3, und von vorne das ganze.
    }

Wenn du dein if durch ein while ersetzt und dann ohne else p++ machst, erhältst du 2*2*2*; bei deinem Code muss 2*4* rauskommen.

Oder die Änderung von @tollertyp, damit nur dann der Faktor erhöht wird, wenn beim Modulo keine 0 rauskommt.

 

[7Jonas7]

Ich habe den Fehler mit den Klammern gefunden, in meinem Programm habe ich sie nicht gesetzt, nur hier im Forum.
Darum funktioniert das bei mir aber bei euch nicht, Entschuldigung

Übrigens reicht es bis zur Wurzel zu vergleichen:
while (p <= sqrt(zahl))

Das funktioniert bei mir nicht, ist aber auch nicht so schlimm.

Eine letzte Frage: ist es mit C++ und Visual Studio möglich, 128-bit integer einzufügen oder geht das nicht?

 

[Revan1710]

Du beötigst ein 128 Bit Integer, was es im Standard allerdings (leider) nicht gibt.

Wieso? 64 Bit sollten völlig ausreichend sein

Ich habe bereits versucht, int mit long int bzw. long long und auch unsigned int zu ersetzen für mehr Speicherplatz, jedoch bringt das nichts

Um platform- /compilerabhänigen Unterschieden aus dem Weg zu gehen würde ich als Datentyp zu uint64_t raten (<cstdint>) bzw. in VS wohl unsigned __int64

 

[BeBur]

Siehe hier: https://stackoverflow.com/a/15400100
Also Boost oder GMP wenn du willst, dass das ganze halbwegs performant mit Zahlen beliebiger Größe Funktioniert.