Problem 7: 10001. Primzahl

Gesucht wird die 10001. Primzahl! [das englische Original]

Genau wie bei Problem 3 kann man hier das „Sieb des Eratosthenes“ verwenden, um die Lösung zu finden. Die Herausforderung besteht allerdings darin, man nicht weiß, wie hoch man die obere Grenze setzen muss, damit am auch die 10001. Primzahl erreicht.

Ich habe dies einfach getestet und konnte bei einer Siebgröße von 500000 die Lösung finden:

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

   max = 500000;
   cnt = 0;

   sieve = new int[ max ];

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

/**
* Runs the algorithm of the "Sieve of Eratosthenes" and count every
* found prime factor. If the 10001. is found, it is returned.
*
* @return the 100001. prime factor
* @see <a href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes">Wikipedia</a>
*/
@Override
public String solve() {

  for( int i=2; i<max; i++ ) {
     if( sieve[ i ] > -1 ) {
        cnt++;
        IO.debugln( cnt + ". prime = " + sieve[ i ] );

        if( cnt == 10001 ) {
           return IO.i2s( sieve[ i ] );
        }

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

   return "-1";
}

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

<< Problem 6 Übersicht Problem 8 >>

Kommentar verfassen

Willkommen in Nico Dannebergs Netzwerk

%d Bloggern gefällt das: