Überprüfen Sie die Primzahl auf große Werte in Java, ohne eingebaute Funktionen zu verwenden.

Question

Ich möchte ein Java-Programm schreiben, um die Primzahl auf große Werte zu überprüfen. Ich hatte diesen Code geschrieben, aber es gibt Fehler in meinem Code. Bitte helfen Sie mir, das zu lösen, damit es für große Werte gut funktioniert.

Auch ist mein Ansatz richtig für die Überprüfung der Primzahl für große Zahlen ohne integrierte Funktionen?

Andere mögliche Lösungen/Ansätze, bitte.

My_Code:

import java.math.*; 
import java.util.Scanner; 
public class CheckPrimeNumber { 
    public static void main(String[] args) 
    { 
     int flag=0; 
     BigInteger input; 
     try{ 
     Scanner sc= new Scanner(System.in); 
     System.out.println("Enter a valid positive number: "); 
     String strinput=sc.nextLine(); 
     input = new BigInteger(strinput); 

     sc.close(); 
     if(input.equals(0) ||input.equals(1)){      
      System.out.println(input+" is not a prime number."); 
      } 
     else{ 
      for(BigInteger i=2; i < input.divide(2); i++){ 
       if(input.remainder(2) == 0){ 
        System.out.println(input+" is not a prime number."); 
        flag=1; 
        break;      
        } 
       } 
       if(flag==0) 
        System.out.println(input +" is a prime number.");    
      } 
     } 
    catch(Exception e){ 
     System.out.println("Please enter only valid positive number: "); 
     } 
    finally{ 
     System.out.println("Thank you...!!!");  
     } 
    } 
} 

Answer 1

Zunächst sollten Sie Ihren Fehler posten.

Ihr Ansatz sollte Eingabe/2 Zahlen überprüfen, um zu sehen, ob sie durch einige Zahlen teilbar sind. Es ist richtig, aber es ist nicht das Beste. Überprüfen Sie andere Hauptalgorithmen auf bessere Leistung.

In der for-Schleife sollten Sie input.remainder (i) anstelle von input.remainder (2) überprüfen.

Answer 2

Ein möglicher Ansatz:

1. prüfen Teilbarkeit durch kleine Primzahlen bis zu etwa 5.000. Dies findet die einfachen.

2. Führen Sie optional einen einzelnen Fermat-Test mit Base 2 durch. Dadurch werden einige weitere Composites zu geringeren Kosten als ein Miller-Rabin-Test eliminiert.

3. Wenn die Nummer noch nicht als zusammengesetzt gekennzeichnet ist, führen Sie wiederholte Miller-Rabin-Tests mit der Genauigkeit durch, die Sie benötigen. Wenn Sie 64 Tests ausführen, beträgt die Wahrscheinlichkeit eines Fehlers weniger als 1 in 2^128.

Vielleicht wollen Sie auch bei einer Kopie von Crandall and Pomerance suchen, die in diesem Bereich sehr nützlich ist.