Fun-Soft - Programmierforum

Autor

Thread - Seiten: > 1 < [ 2 ]

000
07.02.2006, 19:11 Uhr
plooy

Hallo,

vor ein paar Tagen habe ich versucht, ein Programm zu schreiben, das eine Zahl annimmt, erkennt ob diese eine Primzahl ist, und wenn nein, sie in Primfaktoren zerlegt.

Das Programm geht zwar, ich will aber das ganze ohne goto machen, und ich glaube die zwei for-Schleifenkann man in eine packen, denn sie erledigen ja nahezu dieselbe Aufgabe.

C++:

#include <iostream.h>

int main()
{
    cout << "Priemzahlzerlegung\n\n";

    unsigned long Zahl;
    cin >> Zahl;

    if (Zahl==0)
    {
        cout << "Die Zahl sollte schon nicht 0 sein, oder?\n\n";
        cin >> Zahl;
        return 0;
    }

    if(Zahl==1 || Zahl==2)
    {
        cout << "Primzahl!\n";
        cin >> Zahl;
        return 0;
    }

    for(unsigned long i=2; i<=Zahl/2; i++)
    {
        if(Zahl%i==0)    //keine Priemzahl, da Rest = 0
        {
            cout << "Keine Priemzahl!\n";
            goto keinePriemzahl;
        }

        if(i==Zahl/2)
        {
            cout << "Primzahl!\n";
            cin >> Zahl;
            return 0;
        }
    }

keinePriemzahl:

    if(Zahl==1)
    {
        cin >> Zahl;
        return 0;
    }

    for(unsigned long j=2; j<=Zahl; j++)
    {
        if(Zahl%j==0)
        {
            Zahl=Zahl/j;
            cout << j << " ";
            goto keinePriemzahl;
        }
    }

    cin >> Zahl;
    return 0;
}

Noch eine Frage:
Kann man eine while-, eine for- und eine if- Schleife (in dieser Reihenfolge) so machen, dass eine break-Anweisung in der if-Schleife auch die for-Schleife abbricht?
So etwa:

C++:

while(x==y)
{
     for(int i=0; i<x; i++)
     {
           if(x%i==0)
                 break;
      }
}

Danke

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

001
07.02.2006, 19:28 Uhr
Karldin Shinowa
Professional Noob

bin auch ein noob aber kann man goto nicht durch ne funktion ersetzen????

C++:

void keinePrimzahl(unsigned long Zahl)

und dann immer rekursiven aufruf?

war ja nur ne idee

goto = böse^^
--
Ich will die Welt verbessern, doch Gott gibt mir nicht den Code.

Dieser Post wurde am 07.02.2006 um 19:29 Uhr von Karldin Shinowa editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

002
07.02.2006, 21:56 Uhr
CDW

Du brauchst auch nur bis zur Wurzel(Zahl) durchzugehen

, genauso brauchst Du nicht jedesmal mit dem vielfachen von 2 zu dividieren - also eventuell lohnt sich vorher durch zwei zu dividieren und dann eben for (int i=3;i<sqrt(zahl);i=i+2);

geht es auch nicht so?

C++:

boolean check_if_prim (int Zahl){

if (Zahl%2==0) return false;

for(unsigned long i=3; i<=sqrt(Zahl); i++) //oder, wenn der Compiler relativ alt ist bringt auch  eine Auslagerung der Wurzel: vorherige Zeile dann: int Wurzel=sqrt(Zahl) und in der Forschleife eben i<=wurzel)
    {
        if(Zahl%i==0)    //keine Priemzahl, da Rest = 0
        {
            return false;
        }

        if(i==Zahl/2)
        {
            cout << "Primzahl!\n";
            cin >> Zahl;
            return 0;
        }
    }

}

main()
{
   Zahl=einlesen;
   if (Zahl==1 || Zahl==2) .....

   if  (check_if_prim) {
      cout << "Priemzahl!\n";
   } else irgendwas anderes.


}

Naja, so in etwa - ist wahrscheinlich zuviel JavaSyntax drin

--
EB FE

Dieser Post wurde am 07.02.2006 um 21:56 Uhr von CDW editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

003
08.02.2006, 15:59 Uhr
plooy

Danke, ich habe eure Ideen verwenden können. Seht euch das an:

C++:

#include <iostream.h>
#include <math.h>

bool ifPriem(unsigned long);
unsigned long Primzahlzerlegung(unsigned long);

int main()
{
    cout << "Priemzahlzerlegung (v1.1)\n\n";

    while(true)
    {
        unsigned long Zahl;
        cin >> Zahl;

        if(ifPriem(Zahl)==true)
        {
            cout << "Priemzahl!\n\n";
        }
        else
        {
            cout << "Keine Primzahl!\n";
            Primzahlzerlegung(Zahl);
            cout << "\n\n";
        }
    }
    return 0;
}

bool ifPriem(unsigned long Zahl)
{
    if (Zahl==0)
    {
        cout << "Die Zahl sollte schon nicht 0 sein, oder?\n\t(^_^)\n\n";
        return false;
    }

    if(Zahl==1 || Zahl==2 || Zahl==3 || Zahl==5 || Zahl==7)
    {
        return true;
    }

    if(Zahl%2==0)
    {
        return false;
    }

    unsigned long Zahl2=sqrt(Zahl);
    for(unsigned long i=3; i<=Zahl2; i++)
    {
        if(Zahl%i==0)
        {
            return false;
        }

        if(Zahl2==i)
        {
            return true;
        }
    }
}

unsigned long Primzahlzerlegung(unsigned long Zahl)
{
    if(Zahl==1)
    {
        return 0;
    }

    for(unsigned long i=2; i<=Zahl; i++)
    {
        if(Zahl%i==0)
        {
            Zahl/=i;
            cout << i << " ";
            return Primzahlzerlegung(Zahl);
        }
    }
}

Kann man noch etwas verbessern?

Kann man eine while-, eine for- und eine if- Schleife (in dieser Reihenfolge) so machen, dass eine break-Anweisung in der if-Schleife auch die for-Schleife abbricht?
So etwa:

C++:

while(x==y)
{
     for(int i=0; i<x; i++)
     {
           if(x%i==0)
                 break;
      }
}

Danke

Dieser Post wurde am 08.02.2006 um 16:02 Uhr von plooy editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

004
08.02.2006, 16:43 Uhr
predator

Wenn du noch etwas an der Geschwindigkeit feilen willst, musst du die sqrt-Funktion rausschmeißen.
Nimm stattdessen folgende Bedingung in der for-Schleife: i*i<=Zahl.
Multiplizieren ist nämlich schneller als Wurzel ziehen.

Zitat:

... if-Schleife ...

www.if-schleife.de

Zitat:

dass eine break-Anweisung in der if-Schleife auch die for-Schleife abbricht?

Das ist doch schon so. Ein break bricht nie eine if-Abfrage ab, sondern die umgebene Schleife.
--
Gruß
predator

Zitat von Edsger W. Dijkstra:

Es ist praktisch unmöglich, einem Studenten gutes Programmieren beizubringen, wenn er vorher in BASIC programmiert hat. Als potenzielle Programmierer sind sie geistig verstümmelt ohne Hoffnung auf Erholung.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

005
08.02.2006, 17:20 Uhr
plooy

Danke

Kann mir jemand den mathematischen Hintergrund sagen, weshalb ich nur bis Wurzel(Zahl) suchen muss und nicht bis Zahl/2 ?

Und kann ich double anstadt den unsigned long nehmen?
Modulo macht aber bei double Probleme.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

006
08.02.2006, 19:06 Uhr
plooy

i*i<=Zahl
hört sich interessant an, macht aber probleme:
for(unsigned long i=3; i*i<=Zahl; i++)
1. 3 9 zb.11
2. 4 16 11
seht ihr, was ich meine?

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

007
08.02.2006, 19:07 Uhr
predator

Naja, alle Zahlen, die vorkommen müssen ja natürlich sein (siehe Def. von Primzahl).
Angenommen es gilt

Code:

i * x = zahl

1. Möglichkeit:

Code:

i = sqrt(zahl)
=> x = sqrt(zahl)

Wenn i die Wurzel aus zahl ist, muss natürlich auch x die Wurzel aus zahl sein.

2. Möglichkeit:

Code:

i > sqrt(zahl)
=> x < sqrt(zahl)

Wenn i größer als sqrt(zahl) ist, muss x kleiner als sqrt(zahl) sein.

Du teilst in deiner Funktion ifPriem (sollte besser isPrim heißen) mit dem Modulo-Operator ja zahl durch i und überprüfst den Rest.

Wenn du diese Modulo-Operation durchführst, und es wird 0 zurückgegeben, bedeutet dies ja, dass zahl durch i ohne Rest teilbar ist.
Das heißt aber gleichzeitig, dass es eine andere natürliche Zahl x gibt, die mit i multipliziert zahl ergibt, denn

Code:

zahl / i = x (ohne Rest)
zahl = x * i

Wenn i jetzt größer als sqrt(zahl) ist, und die Modulo-Operation 0 zurückgibt, bedeutet dies ja erstens, dass x kleiner als sqrt(zahl) sein muss (s. o.), und somit zweitens (und das ist das entscheidende), dass i in einem früheren Schleifendurchlauf schonmal x war.

Wenn es also bis zur Wurzel aus zahl keine natürlichen Teiler gab, wird es auch bei Werten größer als sqrt(zahl) keine geben. (außer natürlich die Zahl selbst)

Ich hoffe, das war verständlich...
Man hätte es wahrscheinlich viel einfacher erklären können, aber naja.

Zu deiner 2. Frage:
Warum willst du double nehmen?

Das ist doch ein Fließkommatyp, und das dürfen Primzahlen ja nicht sein.
--
Gruß
predator

Zitat von Edsger W. Dijkstra:

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

008
08.02.2006, 19:15 Uhr
plooy

double kann auch größere, natürliche Zahlen (N+0) annehmen, oder?
Danke, predator, ich hab es verstanden, das ist echt interessant!

Dieser Post wurde am 08.02.2006 um 19:17 Uhr von plooy editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

009
08.02.2006, 19:41 Uhr
predator

Zitat von plooy:

i*i<=Zahl
hört sich interessant an, macht aber probleme:
for(unsigned long i=3; i*i<=Zahl; i++)
1. 3 9 zb.11
2. 4 16 11
seht ihr, was ich meine?

Ich weiß nicht ganz, was du meinst...

Zitat von plooy:

double kann auch größere, natürliche Zahlen (N+0) annehmen, oder?

Jein. Zwar kann ein double auch große natürliche Zahlen aufnehmen, aber dafür ist es eigentlich nicht gedacht.
Wenn du große natürliche Werte brauchst, dann kannst du ruhig unsigned long nehmen. Dieser Datentyp kann Werte bis 4.294.967.295 aufnehmen; das sollte eigentlich genügen

--
Gruß
predator

Zitat von Edsger W. Dijkstra:

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

Seiten: > 1 < [ 2 ] [ C / C++ (ANSI-Standard) ]

ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: