素数判定アルゴリズム

たぶんかなり速い。
どれほど巨大な数nでも素数かどうかをnの多項式時間で完了する事が出来る。

以下のテストコードでi7 920で１億回の判定が６００ｍｓだった。
最初から大きい数を判定するようにしている。
判定の内容は入力された数が大きいほど遅くなるので、
１～１億まで順に判定した場合はもっと速いはず。
javaのコレクションの遅さが酷いボトルネックになりそうだからやらないけど
Cとかでこのアルゴリズムを使えば範囲１億の素数探索が１０００ｍｓ未満で終わりそう。

用いた法則性
・３以上の素数は奇数である
・３以上の奇数のうち素数でないものには下記の周期性がある

奇数列
[1, 3, 5, 7, +9, 11, 13, -15, 17, 19, -21, 23, +25, -27, 29, 31, -33, -35, 37, -39, 41, 43]
+は周期スタート、-は周期に属する要素
書ききれないけど要するに素数じゃない要素はいくつかの周期の組み合わせで出てきて、
それらの周期は固定じゃなく次々と出てきて、
周期が出てくる周期が決まっている。

周期　　　　　　　  1,  2,  3,  4,  5,  6,  7

最初の値　　　　　　9, 25, 49, 81,121,　　　　　　　　3,5,7,9,11の二乗数

最初のインデックス　5, 13, 25, 41, 61, 85,　　　　　　差が8,12,16,20で増え方が+4

値の差　　　　　　　6, 10, 14, 18, 22, 26, 30,　　　　+4

インデックスの差　　3,  5,  7,  9, 11, 13, 15,　　　  +2

本当かよ！って思う人はこの数列を見て確かめて下さい。
 [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99, 101, 103, 105, 107, 109, 111, 113, 115, 117, 119, 121, 123, 125, 127, 129, 131, 133, 135, 137, 139, 141, 143, 145, 147, 149, 151, 153, 155, 157, 159, 161, 163, 165, 167, 169, 171, 173, 175, 177, 179, 181, 183, 185, 187, 189, 191, 193, 195, 197, 199, 201, 203, 205, 207, 209, 211, 213, 215, 217, 219, 221, 223, 225, 227, 229, 231, 233, 235, 237, 239, 241, 243, 245, 247, 249, 251, 253, 255, 257, 259, 261, 263, 265, 267, 269, 271, 273, 275, 277, 279, 281, 283, 285, 287, 289, 291, 293, 295, 297, 299, 301, 303, 305, 307, 309, 311, 313, 315, 317, 319, 321, 323, 325, 327, 329, 331, 333, 335, 337, 339, 341, 343, 345, 347, 349, 351, 353, 355, 357, 359, 361, 363, 365, 367, 369, 371, 373, 375, 377, 379, 381, 383, 385, 387, 389, 391, 393, 395, 397, 399, 401, 403, 405, 407, 409, 411, 413, 415, 417, 419, 421, 423, 425, 427, 429, 431, 433, 435, 437, 439, 441, 443, 445, 447, 449, 451, 453, 455, 457, 459, 461, 463, 465, 467, 469, 471, 473, 475, 477, 479, 481, 483, 485, 487, 489, 491, 493, 495, 497, 499, 501, 503, 505, 507, 509, 511, 513, 515, 517, 519, 521, 523, 525, 527, 529, 531, 533, 535, 537, 539, 541, 543, 545, 547, 549, 551, 553, 555, 557, 559, 561, 563, 565, 567, 569, 571, 573, 575, 577, 579, 581, 583, 585, 587, 589, 591, 593, 595, 597, 599, 601, 603, 605, 607, 609, 611, 613, 615, 617, 619, 621, 623, 625, 627, 629, 631, 633, 635, 637, 639, 641, 643, 645, 647, 649, 651, 653, 655, 657, 659, 661, 663, 665, 667, 669, 671, 673, 675, 677, 679, 681, 683, 685, 687, 689, 691, 693, 695, 697, 699, 701, 703, 705, 707, 709, 711, 713, 715, 717, 719, 721, 723, 725, 727, 729, 731, 733, 735, 737, 739, 741, 743, 745, 747, 749, 751, 753, 755, 757, 759, 761, 763, 765, 767, 769, 771, 773, 775, 777, 779, 781, 783, 785, 787, 789, 791, 793, 795, 797, 799, 801, 803, 805, 807, 809, 811, 813, 815, 817, 819, 821, 823, 825, 827, 829, 831, 833, 835, 837, 839, 841, 843, 845, 847, 849, 851, 853, 855, 857, 859, 861, 863, 865, 867, 869, 871, 873, 875, 877, 879, 881, 883, 885, 887, 889, 891, 893, 895, 897, 899, 901, 903, 905, 907, 909, 911, 913, 915, 917, 919, 921, 923, 925, 927, 929, 931, 933, 935, 937, 939, 941, 943, 945, 947, 949, 951, 953, 955, 957, 959, 961, 963, 965, 967, 969, 971, 973, 975, 977, 979, 981, 983, 985, 987, 989, 991, 993, 995, 997, 999]

そして重要なのがその規則性が示す事はnの多項式時間で素数判定が出来るということ。
以下プログラム。

public class PrimeNumber {


public void test(){
int m = 100000000;
long n[] = new long[m];

for(int i=0; i<n.length; i++)
n[i] = i*i*9999999L;

long timer = System.currentTimeMillis();
for(int i=0; i<m; i++){
isPrime(n[i]);
}

System.out.println((System.currentTimeMillis() - timer) + "ms");
}

public static boolean isPrime(long n){
if(n <= 1) return false;
if(n == 2) return true;
if(n%2 == 0) return false;

long interval = 6;
for(int i=3; i*i<n; i+=2){
int j= i*i;
if(((n-j)%interval) == 0){
return false;
}
interval+=4;
}
return true;
}


}