12桁以上の素数を検証するJavaの効率的なアルゴリズムは何ですか？

Question

Javaで効率的なコードを実装して、与えられた数値が12桁以上の大きさの素数であるかどうかを検証する方法は？

例

Input: 
10
Output: prime 
Input: 
101111111111 
Output: prime 
Input: 
101740496633 
Output: prime 
Input: 
111111111111 
Output:not prime 
Input: 
157639024808 
Output: not prime 

私はそれが素数であるかどうかを確認するには、次のアルゴリズムを実装してみました。しかし、 は動作しません。 12桁以上の数値には長すぎます。

マイコード

public static Boolean checkPrime(long a){ 
    if(a%2==0) 
     return false; 
    for(int i=3;i<(int)Math.sqrt(a);i=i+2){ 
     if(a%i==0){ 
      return false; 
     } 
    } 
    return true;  
} 

「」は数が
与えられた数が素数でない場合は与えられた数が素数であるか偽である場合、上記の関数がtrueを返したチェックされます。

12より大きい数値の場合、与えられた数値が素数であるかどうかを調べるにはどうすればよいですか？

Answer 1

1/2の代わりに1/3の値をチェックするだけで、これをわずかに上げることができます。

public static boolean checkPrime(long a) { 
    if (a % 2 == 0) 
     return a == 2; 
    for (int i = 3; i <= (int) Math.sqrt(a); i = i + 2) { 
     if (a % i == 0) { 
      return false; 
     } 
    } 
    return true; 
} 

public static boolean checkPrime2(long a) { 
    if (a % 2 == 0 || a % 3 == 0 || a % 5 == 0) { 
     return a <= 3 || a == 5; 
    } 
    for (int i = 6, max = (int) Math.sqrt(a); i <= max; i = i + 6) { 
     if (a % (i + 1) == 0 | a % (i + 5) == 0) { 
      return false; 
     } 
    } 
    return true; 
} 

public static void time(String desc, BooleanSupplier run) { 
    long start = System.nanoTime(); 
    boolean result = run.getAsBoolean(); 
    if (!result) 
     throw new AssertionError(); 
    long time = System.nanoTime() - start; 
    System.out.printf("%s took %.3f mill-seconds%n", desc, time/1e6); 
} 

public static void main(String... args) { 
    for (int i = 2; i < 1000; i++) { 
     boolean a = checkPrime(i); 
     boolean b = checkPrime2(i); 
     if (a != b) 
      throw new AssertionError(i); 
    } 

    for (int i = 0; i < 3; i++) { 
     time("checkPrime",() -> checkPrime(9999999998987L)); 
     time("checkPrime2",() -> checkPrime2(9999999998987L)); 
    } 
} 

プリント

checkPrime took 26.887 mill-seconds 
checkPrime2 took 13.878 mill-seconds 
checkPrime took 25.527 mill-seconds 
checkPrime2 took 11.286 mill-seconds 
checkPrime took 16.799 mill-seconds 
checkPrime2 took 9.929 mill-seconds 

は、これは、複数のスレッドが役立つだろうことは明らかではないことを十分に小さくなり始めています。