如何检查一个10位数字是否为素数？

Question

我知道Sieve的算法，直到现在我一直在用它来得到高达10亿的素数。

但现在我需要知道一个10位数是素数还是不是素数，而Sieve的算法无法在时间限制内计算出来。

我搜索了很多，找到了费马的素数检验，但它没有成功，因为有些部分我不能理解，而有些部分告诉我，它只是通过一些迭代来判断它是不是可能的素数。

我想知道，在1秒左右的时间内，如何测试一个这么大的数是否为素数？最有效的解决方案/算法是什么？

编辑我还添加了我的代码为筛的算法。

public class Random18 {

    public static int sieveOfEratosthenes(int n) 
    { 
        // Create a boolean array "prime[0..n]" and initialize 
        // all entries it as true. A value in prime[i] will 
        // finally be false if i is Not a prime, else true. 
        boolean primes[] = new boolean[n+1]; 
        Arrays.fill(primes,true);        // assume all integers are prime.

        primes[0]=primes[1]=false;       // we know 0 and 1 are not prime.
        for (int i=2;i<primes.length;i++) {
            //if the number is prime, 
            //then go through all its multiples and make their values false.
            if(primes[i]) {
                for (int j=2;i*j<primes.length;j++) {
                    primes[i*j]=false;
                }
            }
        }
        if(primes[n]==true)
            return 1;

        else
            return 0;
    } 


    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        System.out.println("Enter");

        int p = scanner.nextInt();

        long t1 = System.currentTimeMillis();

        int k = sieveOfEratosthenes(p);

        long t2 = System.currentTimeMillis();

        if(k==1)
            System.out.println("yes");

        else
            System.out.println("no");

        System.out.println("took "+(t2-t1)+" millis");


        scanner.close();
    }

}

像这样的大数字的输出:
999999937
是
用了24363磨机

Answer 1

public static void main(String[] args) {
    try (Scanner scan = new Scanner(System.in)) {
        System.out.print("Enter: ");
        long val = scan.nextLong();
        long t1 = System.currentTimeMillis();
        System.out.println(isPrime.test(val) ? "yes" : "no");
        System.out.println("took " + (System.currentTimeMillis() - t1) + " millis");
    }
}

static final LongPredicate isPrime = val -> {
    if (val < 2)
        return false;

    for (int i = 2, sqrt = (int)Math.sqrt(val); i <= sqrt; i++)
        if (val % i == 0)
            return false;

    return true;
};

输出：

Enter: 999999937
yes
took 1 millis