Problem 3: Größter Primfaktor

Gesucht wird der größte Primfaktor (also ein Faktor, der selbst eine Primzahl ist) der Zahl 600851475143! [das englische Original]

Zur Lösung dieses Problems habe ich mich zum ersten Mal mit dem „Sieb des Eratosthenes“ beschäftigt. Dieses Sieb ist ein alter, aber effektiver Algorithmus, Primzahlen zu finden. Man muss diesen Algorithmus bis maximal zur Wurzel der o.g. Zahl gehen, um den größten Primfaktor zu finden.

In meinem Java-Quellcode habe ich dann auch zum ersten Mal die prepare-Methode überschrieben, da ich das Erstellen des Siebes zeitlich vor dem eigentlichen Lösen des Problems stellen wollte. Die solve-Methode setzt dann „nur“ noch den Algorithmus des Siebes um:

/**
 * Initializes the {@link #sieve} with number from 0 to {@link #sqrtNum}.
 */
@Override
public void prepare() {
   super.prepare();

   num = 600851475143L;
   sqrtNum = 775147; // = int( sqrt( num ) ) + 1

   sieve = new int[ sqrtNum ];

   for( int i=0; i<sqrtNum; i++ ) {
      sieve[ i ] = i;
   }
};

/**
 * Runs the algorithm of the "Sieve of Eratosthenes" and finally finds
 * the largest prime factor.
 *
 * @return the largest prime factor
 * @see <a href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes">Wikipedia</a>
 */
@Override
public String solve() {
   int max = 1;

   for( int i=2; i<sqrtNum; i++ ) { if( sieve[ i ] > -1 ) {
         if( num % i == 0 ) {
            IO.debugln( "next prime: " + i );
            max = i;
         }

         for( int j=i; j<sqrtNum; j+=i ) {
            sieve[ j ] = -1;
         }
      }
   }

   return IO.i2s( max );
}

Den vollständigen Quellcode der Klasse für die Lösung des Problems 3 kann man sich hier anschauen!

<< Problem 2 Übersicht Problem 4 >>

Kommentar verfassen

Willkommen in Nico Dannebergs Netzwerk

%d Bloggern gefällt das: