Algorithmus um nächst folgende Primzahl zu berechnen

[sh33p]

Ich überlege mir gerade, wie man einen algorithmus definieren kann, der bei einer eingebenen zahl prim die nächste primzahl liefert..
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31

bis zur zahl 13 sieht das alles super aus,da is bis auf 2->3 immer 2er Abstände sind.

public class SuccPrim {



  public static void main(String[] args) {
  
  Scanner scan = new Scanner(System.in);
  System.out.println("Bitte geben Sie die Primzahl ein");
  int primzahl = scan.nextInt();

  System.out.println(Prim(primzahl));
  }
  
  public static int Prim(int prim){
  int ergebnis;
  if(prim==2){
  ergebnis = 3;
  return ergebnis;

  }else{

      prim = prim+2;
      ergebnis = prim;
      return ergebnis;
    }
  }


  }

Wie kann ich einen Alg. schreiben,der wirklich, unabhängig welche Primzahl eingeben wurde, die nächste Primzahl in der Folge liefert? Die Prüfung,ob die eingebene Zahl wirklich eine Primzahl ist,soll hier mal außenvor stehen

 

[Ebenius]

Wie kann ich einen Alg. schreiben,der wirklich, unabhängig welche Primzahl eingeben wurde, die nächste Primzahl in der Folge liefert? Die Prüfung,ob die eingebene Zahl wirklich eine Primzahl ist,soll hier mal außenvor stehen

Ohne alle kleineren Primzahlen zu kennen? Wenn Du das löst, dann bezahlt Dir jeder Geheimdienst der Welt eine Menge Geld (oder erschießt Dich).

🙂

Ebenius

 

[nrg]

stimmt. sind ja ganze 4 😀

 

[DocTylerDurden]

wie die folge der primzahlen definiert ist weiß nur gott. du wirst also nich drumrumkommen einfach nur bei den höheren zahlen auszuprobieren obs primzahlen sind.

 

[sh33p]

alles klar 😀

 

[nrg]

z.b.

public class Prime {
	static int[] lowPrimes = { 2, 3, 5, 7 };
	public static void main( String[] args) {
		System.out.println( nextPrime( 73 ) );
	}
	public static int nextPrime( int prime ) {
		while ( !isPrime( ++prime ) );
		return prime;
	}
	public static boolean isPrime( int prime ) {
		for ( int i : lowPrimes )
			if ( prime % i == 0 && prime != i ) return false;
		return true;
	}
}

 

[JohannisderKaeufer]

z.b.

public class Prime {
	static int[] lowPrimes = { 2, 3, 5, 7 };
	public static void main( String[] args) {
		System.out.println( nextPrime( 73 ) );
	}
	public static int nextPrime( int prime ) {
		while ( !isPrime( ++prime ) );
		return prime;
	}
	public static boolean isPrime( int prime ) {
		for ( int i : lowPrimes )
			if ( prime % i == 0 && prime != i ) return false;
		return true;
	}
}

Nur das das bei isPrime(121) true rauskommt, wo false drin sein soll.
11 * 11 = 121 und 11 ist nicht in deinen lowPrimes enthalten.

Und irgendwoher müßen die lowPrimes ja herkommen. Also irgend ein Orakel muß dir schon die low Primes verraten, oder du mußt sie berechnen. Dann kannst du aber das schließen auf die nächste Primzahl einer gegebenen Zahl auch seinlassen.

Was funktioniert ist ein Algorithmus der als Abbruchkriterium die Quadratwurzel einer zu überprüfenden Zahl berücksichtigt.

public static boolean isPrime( int prime ) {
int sqrt = Math.sqrt(prime);
		for ( int i : lowPrimes ){
                        if ( i > sqrt) return false;
			if ( prime % i == 0 && prime != i ) return false;
}
		return true;
	}

das kann den Algorithmus schon wesentlich beschleunigen, so daß nur potentielle Primfaktoren berücksichtigt werden. Ist ein Primfaktor größer als sqrt, dann ist mindestens ein anderer kleiner als sqrt. Bei einer Primzahl ist das egal, bei einem Primzahlkandidaten spart es je größer er ist enorm.

Bleibt allerdings die Frage wie man zu den lowPrimes kommt.

Indem man sie generiert.

public static boolean isPrime( int prime ) {
int sqrt = Math.sqrt(prime);
int i = nextPrime(1);
while ( i<= sqrt ){
	if ( prime % i == 0 && prime != i ) return false;
              i = nextPrime(i);
}
		return true;
	}

Da ich das ganze jetzt nicht laufen lasse, versteht sich um die Zeit müßte lediglich ein next Prime ergänzt werden um eine Endlos Schleife/Rekursion zu umgehen.

public static int nextPrime( int prime ) {
if(prime == 1) return 2;
		while ( !isPrime( ++prime ) );
		return prime;
	}

Würd mich mal interessieren ob das läuft?

 

[Landei]

Prinzipiell ist es ein großer Unterschied, ob man alle Primzahlen von 2 bis zu einer gegebenen Grenze berechnen will (dann bietet sich das Sieb des Eratosthenes oder - komplexer und schneller - des Atkin an) oder nur eine bestimmte Zahl testen will. Für größere Zahlen ist es ratsam, erst einmal einen schnellen probablistischen Primzahltest zu machen (der eine minimale Wahrscheinlichkeit hat, auch bestimmte zusammengesetzte Zahlen als prim zu melden), etwa Miller-Rabin. Insgesamt gibt es eine fast biologische Vielfalt an Primzahltests, z.B. auch Varianten, die nur für bestimmte Zahlentypen funktionieren (etwa Lucas-Lehmer für Mersenne-Primzahlen). Damit nicht zu verwechseln sind Verfahren zum bestimmen der Primfaktoren, die wesentlich langsamer sind (auf dieser Asymmetrie beruhen Verschlüsselungsverfahren wie RSA).