Primfaktorzerlegung

[Murcks]

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!

[TDM]

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;

}

[Murcks]

Naja, Arrays darfste net benutzen...

[Klotzkopp]

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.

[Klotzkopp]

Naja, Arrays darfste net benutzen...

Muss man auch nicht.

Wie würdest du denn eine Primfaktorzerlegung von Hand machen? Das ist meist kein schlechter Ansatz für einen Algorithmus.

[TDM]

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

[Klotzkopp]

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.

[UltimateRuppi]

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

[TDM]

Ich habe den Fehler bemerkt, und die Zahl auf 143 geändert. Du bist dran.

Wie kommst du auf 143 ? O.o

[Klotzkopp]

Wie kommst du auf 143 ? O.o

Das ist die kleinste Zahl, die nicht durch 2, 3, 5 oder 7 teilbar ist, aber trotzdem keine Primzahl ist - außer nach deiner "Definition".

143 = 11 * 13

Ich merke gerade, 121 hätte es auch getan.

[Guybrush Threepwood]

Eine Primzahl würde ich so ermitteln:

bool Primzahl(const unsigned int &iZahl)

{

    if (iZahl<2) 

		return false;

    if(iZahl==2 || iZahl==3) 

		return true;

    if (iZahl%2==0) 

		return false;

    for(unsigned int i=3;i*i<=iZahl;i+=2)

        if(iZahl%i==0) 

			return false;

	return true;

}

[/PHP]

[TDM]

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)

[UltimateRuppi]

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

[Klotzkopp]

TDM: Sieht gut aus.

Ich bin eher ein Freund der einfachen Lösungen

#include <iostream>


int main()

{

	int n;

	std::cin >> n;

	while(n>1)

	{

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

		{

			if(n % t == 0)

			{

				std::cout << t << ' ';

				n /= t;

				break;

			}

		}

	}

}[/code]

[UltimateRuppi]

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