Primzahlenerzeugung mit Java (was: Mathematik- und Logikverständnis von ChatGPT)

[Stefan Ram]

Newsgroups: de.sci.mathematik,de.comp.lang.java

"Java-Kode" oder "Java-Code"¹

number = 3;
while(number < 10000) { ...
for(int i = 2; i * i < number; i++) {
if (number%i == 0) { ...
number++;
..

Ist außerhalb des Kontexts und mit den Auslassungen für mich
nicht bewertbar.

Die Methode "nextProbablePrime" gehört zur Standardbibliothek
von Java und soll die nächste Primzahl liefern. Dabei soll
sie keine Primzahl übersehen, aber könnte auch einmal eine
Zahl liefern, die keine Primzahl ist.

Ich wollte diese Methode gerne einmal verwenden, so daß ich
damit auf das folgende Programm zur Ausgabe der ersten
10.000 Primzahlen komme. Da dieses Programm aber "BigInteger"-
Objekte verwendet, obwohl dies hier wohl gar nicht nötig ist,
dürfte es nicht besonders schnell sein.

(Das Hauptprogramm steht weiter unten, hinter "public static
void main".)

public final class Main
{ final static java.math.BigInteger two =
java.math.BigInteger.valueOf( 2 );

final static java.math.BigInteger three =
java.math.BigInteger.valueOf( 3 );

public static boolean two_divides
( final java.math.BigInteger number )
{ return java.math.BigInteger.ZERO.equals
( number.mod( two )); }

public static boolean prime( final java.math.BigInteger number )
{ if( number.equals( two ))return true;
if( two_divides( number ))return false;
for
( java.math.BigInteger i = three;
i.multiply( i ).compareTo( number )< 1;
i = i.add( two ))
if( java.math.BigInteger.ZERO.equals( number.mod( i )))
return false;
return true; }

public static void main( final java.lang.String[] args )
{ final int number_of_primes_to_print = 10_000;
java.math.BigInteger number = java.math.BigInteger.valueOf( 0 );
int number_of_primes_printed = 0;
while( number_of_primes_printed < number_of_primes_to_print )
{ number = number.nextProbablePrime();
if( prime( number ))
{ java.lang.System.out.println( number );
++number_of_primes_printed; }}}}

Newsgroups: de.sci.mathematik,de.comp.lang.java

[Christian Garbs]

Mahlzeit!

Post by Stefan Ram
public static boolean prime( final java.math.BigInteger number )
{ if( number.equals( two ))return true;
if( two_divides( number ))return false;
for
( java.math.BigInteger i = three;
i.multiply( i ).compareTo( number )< 1;
i = i.add( two ))
if( java.math.BigInteger.ZERO.equals( number.mod( i )))
return false;
return true; }

Die schreibst, dass das langsam läuft wegen der BigInteger.

Vielleicht lohnt es sich, vor der Schleife die Abbruchbedingung
einmalig als Quadratwurzel von number zu errechnen, statt bei jedem
Schleifendurchlauf das i zu quadrieren.

Gruß
Christian

[Thomas Noll]

Post by Christian Garbs
Mahlzeit!

Post by Stefan Ram
public static boolean prime( final java.math.BigInteger number )
{ if( number.equals( two ))return true;
if( two_divides( number ))return false;
for
( java.math.BigInteger i = three;
i.multiply( i ).compareTo( number )< 1;
i = i.add( two ))
if( java.math.BigInteger.ZERO.equals( number.mod( i )))
return false;
return true; }

Die schreibst, dass das langsam läuft wegen der BigInteger.

Ja. Er schreibt auch, daß er weiß, daß BigInteger gar nicht nötig sind.

Post by Christian Garbs
Vielleicht lohnt es sich, vor der Schleife die Abbruchbedingung
einmalig als Quadratwurzel von number zu errechnen, statt bei jedem
Schleifendurchlauf das i zu quadrieren.

Eher nicht. Die Dokumentation zu nextProbablePrime sagt:
"The probability that the number returned by this method is composite
does not exceed 2^-100."
Das für eine Stichprobe von ca 2^16 zu prüfen ist einfach
Energieverschwendung.