3. long interger zu klein? oder 'Größter Primfaktor' //Project Euler

long interger zu klein? oder 'Größter Primfaktor' //Project Euler

  • K

    Moin,
    ich bearbeite ein paar Aufgaben von http://projecteuler.net/problems;page=1 .
    Zur Zeit bin ich bei Aufgabe 3 und hab diese auch schon so gut wie gelöst.
    Aufgabe:
    The prime factors of 13195 are 5, 7, 13 and 29.
    What is the largest prime factor of the number 600851475143 ?

    Ich verallgemeiner immer die Aufgaben, sodass ich auch mit anderen Werten 'spielen' kann.
    Wenn ich nun in meinem Programm 13195 eingebe, bekomme ich auch als Lösung 29, 13, 7 und 5.
    Bei 600851475143 kommt einfach nichts. Ist ein unsigned long int zu klein?

    #include <iostream>

using namespace std;

int main () {

	long int x, i = 1, iValue, iFactor;

	cout << "Calculate the prime factors of the number: ";
	cin  >> iValue;

	iFactor = iValue;	// to calculate with modulo later

	for (iValue; iValue > i; iValue--) { //Primefactor backwards, beginn with highest prime value.

		for (x = 2; x < iValue; x++) {

			if (iValue % x == 0) break; // if "non-prime"
		}
			if (iValue == x && iFactor % iValue == 0) { // found prime value, can 'iFactor' be divided through this value? if yes, gotcha!

				cout << "Prim: " << iValue << endl;
			}
	}
	system ("PAUSE");
}
    0
  • ?

    Wenn ja, dann nimm long long

    0
  • K

    long long schrieb:

    Wenn ja, dann nimm long long

    passiert nichts 😞
    Kann's sein das der n bissl länger braucht um das ganze zu lösen, weil das Programm wohl relativ uneffizient ist, wie mir auch selber auffällt.
    Ich lass den Lappi mal 30min mit unsigned long long int arbeiten.

    0
  • ?

    Nein, das passt sogar in einen int.

    Dein Programm ist einfach zu langsam. Du führst 600851475143 mal die innere Schleife aus, die jedesmal selbst wieder 0.5*600851475143 Operationen benötigt. Also führst etwa 10^22 Operationen aus. Zum Vergleich: 10^8 sind etwa eine Sekunde.

    Tipp: Mach ganz normal Primfaktorzerlegung von iValue.

    0
  • C

    toslow schrieb:

    Nein, das passt sogar in einen int.

    Nicht in meins.
    Wohl aber in ein long long.

    0
  • T

    Das Programm arbeitet einfach zu langsam. Du brauchst eine effizientere Methode. Ansetzen kann man da an vielen Stellen.
    Man könnte z.B. mit dem Sieb des Eratosthenes Primzahlen ermitteln (das ist sehr schnell) und dann deine Zahl darauf überprüfen, ob sie durch diese Primzahlen teilbar ist. Oder du fängst mit kleinen Primzahlen an und wenn diese deine Zahl teilen, dann teile sie auch durch diese. Damit wird sie immer kleiner. Am Schluss bleibt der größte Primfaktor übrig. Oder die Faktorisierungsmethode von Fermat: http://de.wikipedia.org/wiki/Faktorisierungsverfahren#Faktorisierungsmethode_von_Fermat oder eine der anderen Methoden dort. Du führst in deinem Programm die reine Probedivision durch. Diese ist nunmal die langsamste Faktorisierungsmethode.

    Habs gerade mal rausgekramt. Hatte es damals auch mit der Probedivision gelöst, die Zahl aber noch geteilt. Läuft in wenigen ms:

    #include <iostream>
using namespace std ;

bool istPrim( long long n )
{
	for ( int i = 2 ;  i < n ;  ++i )
		if ( n % i == 0 )
			return false ;

	return true ;
}

void primfaktorzerlegung( long long n )
{
	for ( int i = 2 ;  i <= n ;  ++i )
		if ( istPrim( i ) ) // ist i Primzahl?
			if ( n % i == 0 ) // ist i ein Primfaktor von n?
			{
				n /= i ; // teile n durch den Primfaktor von n
				cout << i << endl ; // gebe Primfaktor aus
				i = 1 ; // beginne Schleife von vorne
			}
}

int main ()
{
	primfaktorzerlegung( 600851475143LL ) ;

	return 0 ;
}

    Bei späteren Aufgaben kommst du um Sieb des Eratosthenes und die anderen Faktorisierungsverfahren sowie eigene Varianten davon aber nicht mehr drumherum 😉

    0
  • O

    Thilo87 schrieb:

    Habs gerade mal rausgekramt. Hatte es damals auch mit der Probedivision gelöst, die Zahl aber noch geteilt. Läuft in wenigen ms:

    Noch zwei Tipps: (1) Schleife nur bis sqrt(n), (2) n%2 vor die Schleife ziehen und dafür statt ++i ein i+=2 und Start mit i=3. Das eliminiert die überflüssige Überprüfungen von geraden Zahlen.

    0

  • Hallo Thilo87,

    warum überprüfst du erst, ob es eine Primzahl ist und erst danach die Teilbarkeit?
    So wäre es doch noch performanter:

    if ( n % i == 0 ) // ist i ein Primfaktor von n?
    if ( istPrim( i ) ) // ist i Primzahl?

    Außerdem brauchst du jeweils nur bis n/2 (bzw. noch besser sqrt(n)) laufen...

    Es gibt aber noch weitere Optimierungsmöglichkeiten und, wie du selbst geschrieben hast, noch bessere Verfahren.

    Edit: ja, das mit (i=3; ...; i+=2) selbstverständlich auch 😉

    0
Anmelden zum Antworten