在不使用内置函数的情况下检查java中的大值的素数。

Question

我想写一个java程序来检查大值的素数。我写过这段代码，但我的代码中有错误。请帮助我解决这个问题，以便它适用于大值。

另外，我的方法是否适合在没有内置函数的情况下检查大数字的素数？

请提供其他可能的解决方案/方法。

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

一种可能的方法：

1. 用小素数检查可分性，比如5000。这找到了容易的。
2. 可选地，运行单个Fermat测试，基础2.这将比Miller-Rabin测试以更低的成本消除更多的复合材料。
3. 如果该数字尚未标记为复合，则将重复的Miller-Rabin测试运行到您需要的准确度。如果您运行64次测试，那么错误的几率在2 ^ 128中小于1。

您可能还想查看一份在这方面非常有用的Crandall and Pomerance副本。

Answer 2

首先，你应该发布你的错误。

你的方法应该检查输入/ 2号码，看看它们是否可以被某些数字整除。这是对的，但并不是最好的。检查其他主要算法以获得更好的性能

在for循环中，您应该检查input.remainder（i）而不是input.remainder（2）。