アンドロイド端末用の素数判定アプリを作成した際に下記の様なコードを書いた。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
final long N = 5915587277L; boolean flag = true; if(N < 2){ flag = false; } else if(N%2 == 0){ flag = false; } else{ for(long i = 3; i <= Math.sqrt(N); i+=2){ if(N%i == 0){ flag = false; break; } } } if(flag){ System.out.println("This number is a prime number"); } else{ System.out.println("This number isn't a prime number"); } |
これである程度判定が速くなる。アルゴリズム自体は非常に単純。スマホでも１０桁の素数判定に１秒もかからない。もう少し桁数増やすかな。
