Zum Inhalt springen

Primfaktorzerlegung


Murcks

Empfohlene Beiträge

Hallo!

Und wieder eine Klausuraufgabe!

Aufgabe:

Ein Programm schreiben, welches überprüft, ob die eingegebene Zahl eine Primzahl ist oder eben nicht.

Hab ich gemacht und das Programm funktioniert und sieht folgendermaßen aus:

#include <iostream.h>

void main()

{

int num;

int rest;

int div;

while ( true )

{

int count = 0;

cout << "Geben Sie eine Zahl ein: ";

cin >> num;

cout << endl;

for ( int i = 1; i < num; i++ )

{

rest = num % i;

if ( rest == 0 ) count += 1;

}

if ( count == 1 ) cout << "Primzahl!" << endl << endl;

else cout << "Keine Primzahl!" << endl << endl;

}

}

Zusatzaufgabe:

Jetzt soll dieses Programm zusätzlich folgendes machen:

Wenn die eingegebene Zahl keine Primzahl ist, soll zusätzlich die Primfaktorzerlegung ausgegeben werden, z.B. 30 = 2 * 3 * 5.

Hab allerdings keinen Ansatzpunkt...

Diesmal darf ich nur Operatoren, If-Anweisungen, iostream.h und Schleifen (for, do-while, while) benutzen!

Link zu diesem Kommentar
Auf anderen Seiten teilen

du durchsuchst erstmal eine Zahl ob es eine Primzahl ist, wenn du dies machst, und dies keine ist, dann speicherst du dir einfach den faktoren in nem Array und gibst am Ende den Array zurück.


#define MAX_PRIMFAKTOREN 255


bool isPrimzahl(int x)

{

      int faktor = 2;

      while (faktor <= 7) //alternativ auch x/2

      {

            if ((x % faktor) == 0) return false

            faktor++;

      }

      return true;

}


int* Primfaktor (int x)

{

      int faktor = 2;

      int i = 0, int pnResult[MAX_PRIMFAKTOREN];

      pnResult[i] = 0; //erste auf 0 setzen falls es doch eine Primzahl ist

      while (faktor < (x/2))

      {

            if ((x % faktor) == 0)

                if (isPrimzahl(faktor))

                    pnResult[i] = faktor;

            i++;

            faktor++;

      }

      return pnResult;

}

Link zu diesem Kommentar
Auf anderen Seiten teilen

while (faktor <= 7) //alternativ auch x/2
"Alternativ" ist gut.

<= 7 ist schlicht falsch. 143 ist keine Primzahl.

int i = 0, int pnResult[MAX_PRIMFAKTOREN];

...

return pnResult;

Aua, aua. Du gibst die Adresse einer lokalen Variablen zurück -> Bumm.

Dein Algorithmus liefert außerdem keine Primfaktorzerlegung, sondern eine (unvollständige) Teilerliste, verteilt in dem Array zwischen vielen uninitialiserten Werten.

Link zu diesem Kommentar
Auf anderen Seiten teilen

"Alternativ" ist gut.

<= 7 ist schlicht falsch. 99 ist keine Primzahl.

99 ist ja durch 3 teilbar also würde der da schon zurückgeben, dass es keine ist. Alle zahlen die keine Primzahlen sind setzen sich aus 2, 3, 5 und 7 zusammen, ansonsten ist es eine Primzahl

Aua, aua. Du gibst die Adresse einer lokalen Variablen zurück -> Bumm.

Dann halt return *pnResult;

das ist keine unvollständige teilerlist... alles was eine valide zahl ist, ist ein Primzahlfaktor (gut, man hätte den Array vorher mit 0 füllen können...)

Link zu diesem Kommentar
Auf anderen Seiten teilen

99 ist ja durch 3 teilbar also würde der da schon zurückgeben, dass es keine ist. Alle zahlen die keine Primzahlen sind setzen sich aus 2, 3, 5 und 7 zusammen, ansonsten ist es eine Primzahl
Ich habe den Fehler bemerkt, und die Zahl auf 143 geändert. Du bist dran.

Dann halt return *pnResult;
Damit gibst du nur den ersten Eintrag des Arrays zurück. Da steht entweder 2 oder (bei ungeradem x) ein uninitialiserter Wert drin.

das ist keine unvollständige teilerlist... alles was eine valide zahl ist, ist ein Primzahlfaktor (gut, man hätte den Array vorher mit 0 füllen können...)
Dein Algorithmus liefert mehrfach auftretenden Primfaktoren aber nur einmal.
Link zu diesem Kommentar
Auf anderen Seiten teilen

Die Primfaktorzerlegung gestaltet sich am einfachsten, wenn bereits Primzahlen bekannt sind. Dann kann man sich einfach von den kleinen Primzahlen zu de nhohen als Faktoren durchhangeln. Das hat den Vorteil, dass man vorher nicht noch überprüfen ob der Faktorkandidat auch eine Primzahl ist

1. Array mit Primzahlen füllen (wenn nicht erlaubt, dann musst Du halt wirklich jede überprüfen)

2. zu Faktorisierende zahl durch erste Primzahl des array teilen

3. ist die division aufgegangen?

JA => Die Primzahl ist ist ein Primfaktor der Zahl (also Counter für den Wert erhöhen und zu punkt zwei gehen (mit dem divisionsergebnis als neue zahl))

NEIN => Primzahl ist kein Primfaktor (Counter auf 0 setzen, und bei 2. mit nächster primzahl weiter (Zahl ist das letzte bekannte divisionsergebnis ohne Rest)

die schleife ist abbzubrechen wenn das divisionsergebnis 1 ist.

ich hoffe das ist so verständlich, ich möchte den Quellcode hier, zumindest noch nicht, posten ;)

Link zu diesem Kommentar
Auf anderen Seiten teilen

ok, stimmt...

ich mag solche Früh-morgens-Aufgaben nicht :(

naja... ich hab mal bissl rumgetestet

mal sehen ob du wieder Fehler findest Klotzkopp (kann ich nur draus lernen :floet: )


bool teilt (int n, int t); 

bool prim (int n); 

int potenz (int n, int p); 

int main ()

{

	int n;

	int count = 0;

	cin >> n;

	cout << "Primfaktoren von " << n << "\n";

	for (int i=2; i<n; ++i){

		if (teilt (n, i) && prim (i)) {

			cout << i << " hoch " << potenz (n, i) << "\n";

			++count;

		}

	}

	if (count == 0)

		cout << n << " ist eine Primzahl\n";

	else

		cout << endl;

}


bool teilt (int n, int t) 

{

	return (n % t == 0);

}


bool prim (int n) {

	if (n == 2) return true;

	for (int i = 2; i<n; ++i) 

	{ 

		if (teilt (n, i)) return false;

	}

	return true;

}


int potenz (int n, int p) {

	int i = 0,

	pp = 1; 

	while (teilt (n, pp)) {

		++i;

		pp *= p;

	}

	return i-1;

}

müsste eigentlich gehen... bei mir funzt es jedenfalls (angelehnt an UltimateRuppi's Vorschlag)

Link zu diesem Kommentar
Auf anderen Seiten teilen

ok hier meine lösung

Erzeugung des PRimzahlenarrays:


int sieve(long* anPrimes, int nSieveSize)
{
int nPrimesFound;
bool bIsPrime;
int i, p;
int sq;

anPrimes[0] = 2;
anPrimes[1] = 3;
nPrimesFound = 2;

for (i = 5; i <= nSieveSize; i += 2)
{
p = i % 6;
if ( (p == 1) || (p == 5) )
{
bIsPrime = true;

sq = sqrt(i);

for (p = 0; anPrimes[p] <= sq; p++)
{
if ((i % anPrimes[p]) == 0)
{
bIsPrime = false;
break;
}
}

if (bIsPrime)
{
anPrimes[nPrimesFound++] = i;
}
}
}

return nPrimesFound;
}
[/PHP]

Und die Zerlegung in die Faktoren

[PHP]
void factor(int nZahl, long* lpPrimes, int nPrimeCount)
{
int nWork = nZahl;
int nFact = 1;
int i = 0;
int nFactCnt;
bool b = true;

printf ("%d = ", nZahl);
nFactCnt = 0;
while (nWork > 1)
{
if (i >= nPrimeCount)
{
printf("\t- not enough primes to complete operation!");
break;
}

if ((nWork % lpPrimes[i]) == 0)
{
nFactCnt++;
nFact *= lpPrimes[i];
nWork /= lpPrimes[i];
}
else
{
if (nFactCnt == 1)
{
if (i > 0)
{
printf(" * ");
}
printf("%d", lpPrimes[i]);
}
else if (nFactCnt > 1)
{
if (i > 0)
{
printf(" * ");
}
printf("%d^%d", lpPrimes[i], nFactCnt);
}

nFactCnt = 0;
i++;
}
}

if (nFactCnt == 1)
{
if (i > 0)
{
printf(" * ");
}
printf("%d", lpPrimes[i]);
}
else if (nFactCnt > 0)
{
if (i > 1)
{
printf(" * ");
}
printf("%d^%d", lpPrimes[i], nFactCnt);
}

printf("\n");
}

Link zu diesem Kommentar
Auf anderen Seiten teilen

Das geht für einzelne Zerlegungen auch deutlich schneller, nur wenn man tausende davon machen muss, ist die lösung mit dem vorher erstellten primzahlenarray effizienter. Bei meiner Zerlegung geht viel code für die schöne formatierte ausgabe drauf ;)

generating primes array...finished - (664579 primes found in 11469 ms).

106748928 = 2^10 * 3^6 * 11 * 13

Press any key to continue

Link zu diesem Kommentar
Auf anderen Seiten teilen

Dein Kommentar

Du kannst jetzt schreiben und Dich später registrieren. Wenn Du ein Konto hast, melde Dich jetzt an, um unter Deinem Benutzernamen zu schreiben.

Gast
Auf dieses Thema antworten...

×   Du hast formatierten Text eingefügt.   Formatierung wiederherstellen

  Nur 75 Emojis sind erlaubt.

×   Dein Link wurde automatisch eingebettet.   Einbetten rückgängig machen und als Link darstellen

×   Dein vorheriger Inhalt wurde wiederhergestellt.   Editor leeren

×   Du kannst Bilder nicht direkt einfügen. Lade Bilder hoch oder lade sie von einer URL.

Fachinformatiker.de, 2024 by SE Internet Services

fidelogo_small.png

Schicke uns eine Nachricht!

Fachinformatiker.de ist die größte IT-Community
rund um Ausbildung, Job, Weiterbildung für IT-Fachkräfte.

Fachinformatiker.de App

Download on the App Store
Get it on Google Play

Kontakt

Hier werben?
Oder sende eine E-Mail an

Social media u. feeds

Jobboard für Fachinformatiker und IT-Fachkräfte

×
×
  • Neu erstellen...