sieve_test.go

package math

import (
	"testing"
)

var (
	// https://en.wikipedia.org/wiki/List_of_prime_numbers#The_first_1000_prime_numbers
	FirstThousandPrimes = []uint64{
		/* Prime[0] = */ 2,
		/* Prime[1] = */ 3,
		/* Prime[2] = */ 5,
		/* Prime[3] = */ 7,
		/* Prime[4] = */ 11,
		/* Prime[5] = */ 13,
		/* Prime[6] = */ 17,
		/* Prime[7] = */ 19,
		/* Prime[8] = */ 23,
		/* Prime[9] = */ 29,
		/* Prime[10] = */ 31,
		/* Prime[11] = */ 37,
		/* Prime[12] = */ 41,
		/* Prime[13] = */ 43,
		/* Prime[14] = */ 47,
		/* Prime[15] = */ 53,
		/* Prime[16] = */ 59,
		/* Prime[17] = */ 61,
		/* Prime[18] = */ 67,
		/* Prime[19] = */ 71,
		/* Prime[20] = */ 73,
		/* Prime[21] = */ 79,
		/* Prime[22] = */ 83,
		/* Prime[23] = */ 89,
		/* Prime[24] = */ 97,
		/* Prime[25] = */ 101,
		/* Prime[26] = */ 103,
		/* Prime[27] = */ 107,
		/* Prime[28] = */ 109,
		/* Prime[29] = */ 113,
		/* Prime[30] = */ 127,
		/* Prime[31] = */ 131,
		/* Prime[32] = */ 137,
		/* Prime[33] = */ 139,
		/* Prime[34] = */ 149,
		/* Prime[35] = */ 151,
		/* Prime[36] = */ 157,
		/* Prime[37] = */ 163,
		/* Prime[38] = */ 167,
		/* Prime[39] = */ 173,
		/* Prime[40] = */ 179,
		/* Prime[41] = */ 181,
		/* Prime[42] = */ 191,
		/* Prime[43] = */ 193,
		/* Prime[44] = */ 197,
		/* Prime[45] = */ 199,
		/* Prime[46] = */ 211,
		/* Prime[47] = */ 223,
		/* Prime[48] = */ 227,
		/* Prime[49] = */ 229,
		/* Prime[50] = */ 233,
		/* Prime[51] = */ 239,
		/* Prime[52] = */ 241,
		/* Prime[53] = */ 251,
		/* Prime[54] = */ 257,
		/* Prime[55] = */ 263,
		/* Prime[56] = */ 269,
		/* Prime[57] = */ 271,
		/* Prime[58] = */ 277,
		/* Prime[59] = */ 281,
		/* Prime[60] = */ 283,
		/* Prime[61] = */ 293,
		/* Prime[62] = */ 307,
		/* Prime[63] = */ 311,
		/* Prime[64] = */ 313,
		/* Prime[65] = */ 317,
		/* Prime[66] = */ 331,
		/* Prime[67] = */ 337,
		/* Prime[68] = */ 347,
		/* Prime[69] = */ 349,
		/* Prime[70] = */ 353,
		/* Prime[71] = */ 359,
		/* Prime[72] = */ 367,
		/* Prime[73] = */ 373,
		/* Prime[74] = */ 379,
		/* Prime[75] = */ 383,
		/* Prime[76] = */ 389,
		/* Prime[77] = */ 397,
		/* Prime[78] = */ 401,
		/* Prime[79] = */ 409,
		/* Prime[80] = */ 419,
		/* Prime[81] = */ 421,
		/* Prime[82] = */ 431,
		/* Prime[83] = */ 433,
		/* Prime[84] = */ 439,
		/* Prime[85] = */ 443,
		/* Prime[86] = */ 449,
		/* Prime[87] = */ 457,
		/* Prime[88] = */ 461,
		/* Prime[89] = */ 463,
		/* Prime[90] = */ 467,
		/* Prime[91] = */ 479,
		/* Prime[92] = */ 487,
		/* Prime[93] = */ 491,
		/* Prime[94] = */ 499,
		/* Prime[95] = */ 503,
		/* Prime[96] = */ 509,
		/* Prime[97] = */ 521,
		/* Prime[98] = */ 523,
		/* Prime[99] = */ 541,
		/* Prime[100] = */ 547,
		/* Prime[101] = */ 557,
		/* Prime[102] = */ 563,
		/* Prime[103] = */ 569,
		/* Prime[104] = */ 571,
		/* Prime[105] = */ 577,
		/* Prime[106] = */ 587,
		/* Prime[107] = */ 593,
		/* Prime[108] = */ 599,
		/* Prime[109] = */ 601,
		/* Prime[110] = */ 607,
		/* Prime[111] = */ 613,
		/* Prime[112] = */ 617,
		/* Prime[113] = */ 619,
		/* Prime[114] = */ 631,
		/* Prime[115] = */ 641,
		/* Prime[116] = */ 643,
		/* Prime[117] = */ 647,
		/* Prime[118] = */ 653,
		/* Prime[119] = */ 659,
		/* Prime[120] = */ 661,
		/* Prime[121] = */ 673,
		/* Prime[122] = */ 677,
		/* Prime[123] = */ 683,
		/* Prime[124] = */ 691,
		/* Prime[125] = */ 701,
		/* Prime[126] = */ 709,
		/* Prime[127] = */ 719,
		/* Prime[128] = */ 727,
		/* Prime[129] = */ 733,
		/* Prime[130] = */ 739,
		/* Prime[131] = */ 743,
		/* Prime[132] = */ 751,
		/* Prime[133] = */ 757,
		/* Prime[134] = */ 761,
		/* Prime[135] = */ 769,
		/* Prime[136] = */ 773,
		/* Prime[137] = */ 787,
		/* Prime[138] = */ 797,
		/* Prime[139] = */ 809,
		/* Prime[140] = */ 811,
		/* Prime[141] = */ 821,
		/* Prime[142] = */ 823,
		/* Prime[143] = */ 827,
		/* Prime[144] = */ 829,
		/* Prime[145] = */ 839,
		/* Prime[146] = */ 853,
		/* Prime[147] = */ 857,
		/* Prime[148] = */ 859,
		/* Prime[149] = */ 863,
		/* Prime[150] = */ 877,
		/* Prime[151] = */ 881,
		/* Prime[152] = */ 883,
		/* Prime[153] = */ 887,
		/* Prime[154] = */ 907,
		/* Prime[155] = */ 911,
		/* Prime[156] = */ 919,
		/* Prime[157] = */ 929,
		/* Prime[158] = */ 937,
		/* Prime[159] = */ 941,
		/* Prime[160] = */ 947,
		/* Prime[161] = */ 953,
		/* Prime[162] = */ 967,
		/* Prime[163] = */ 971,
		/* Prime[164] = */ 977,
		/* Prime[165] = */ 983,
		/* Prime[166] = */ 991,
		/* Prime[167] = */ 997,
		/* Prime[168] = */ 1009,
		/* Prime[169] = */ 1013,
		/* Prime[170] = */ 1019,
		/* Prime[171] = */ 1021,
		/* Prime[172] = */ 1031,
		/* Prime[173] = */ 1033,
		/* Prime[174] = */ 1039,
		/* Prime[175] = */ 1049,
		/* Prime[176] = */ 1051,
		/* Prime[177] = */ 1061,
		/* Prime[178] = */ 1063,
		/* Prime[179] = */ 1069,
		/* Prime[180] = */ 1087,
		/* Prime[181] = */ 1091,
		/* Prime[182] = */ 1093,
		/* Prime[183] = */ 1097,
		/* Prime[184] = */ 1103,
		/* Prime[185] = */ 1109,
		/* Prime[186] = */ 1117,
		/* Prime[187] = */ 1123,
		/* Prime[188] = */ 1129,
		/* Prime[189] = */ 1151,
		/* Prime[190] = */ 1153,
		/* Prime[191] = */ 1163,
		/* Prime[192] = */ 1171,
		/* Prime[193] = */ 1181,
		/* Prime[194] = */ 1187,
		/* Prime[195] = */ 1193,
		/* Prime[196] = */ 1201,
		/* Prime[197] = */ 1213,
		/* Prime[198] = */ 1217,
		/* Prime[199] = */ 1223,
		/* Prime[200] = */ 1229,
		/* Prime[201] = */ 1231,
		/* Prime[202] = */ 1237,
		/* Prime[203] = */ 1249,
		/* Prime[204] = */ 1259,
		/* Prime[205] = */ 1277,
		/* Prime[206] = */ 1279,
		/* Prime[207] = */ 1283,
		/* Prime[208] = */ 1289,
		/* Prime[209] = */ 1291,
		/* Prime[210] = */ 1297,
		/* Prime[211] = */ 1301,
		/* Prime[212] = */ 1303,
		/* Prime[213] = */ 1307,
		/* Prime[214] = */ 1319,
		/* Prime[215] = */ 1321,
		/* Prime[216] = */ 1327,
		/* Prime[217] = */ 1361,
		/* Prime[218] = */ 1367,
		/* Prime[219] = */ 1373,
		/* Prime[220] = */ 1381,
		/* Prime[221] = */ 1399,
		/* Prime[222] = */ 1409,
		/* Prime[223] = */ 1423,
		/* Prime[224] = */ 1427,
		/* Prime[225] = */ 1429,
		/* Prime[226] = */ 1433,
		/* Prime[227] = */ 1439,
		/* Prime[228] = */ 1447,
		/* Prime[229] = */ 1451,
		/* Prime[230] = */ 1453,
		/* Prime[231] = */ 1459,
		/* Prime[232] = */ 1471,
		/* Prime[233] = */ 1481,
		/* Prime[234] = */ 1483,
		/* Prime[235] = */ 1487,
		/* Prime[236] = */ 1489,
		/* Prime[237] = */ 1493,
		/* Prime[238] = */ 1499,
		/* Prime[239] = */ 1511,
		/* Prime[240] = */ 1523,
		/* Prime[241] = */ 1531,
		/* Prime[242] = */ 1543,
		/* Prime[243] = */ 1549,
		/* Prime[244] = */ 1553,
		/* Prime[245] = */ 1559,
		/* Prime[246] = */ 1567,
		/* Prime[247] = */ 1571,
		/* Prime[248] = */ 1579,
		/* Prime[249] = */ 1583,
		/* Prime[250] = */ 1597,
		/* Prime[251] = */ 1601,
		/* Prime[252] = */ 1607,
		/* Prime[253] = */ 1609,
		/* Prime[254] = */ 1613,
		/* Prime[255] = */ 1619,
		/* Prime[256] = */ 1621,
		/* Prime[257] = */ 1627,
		/* Prime[258] = */ 1637,
		/* Prime[259] = */ 1657,
		/* Prime[260] = */ 1663,
		/* Prime[261] = */ 1667,
		/* Prime[262] = */ 1669,
		/* Prime[263] = */ 1693,
		/* Prime[264] = */ 1697,
		/* Prime[265] = */ 1699,
		/* Prime[266] = */ 1709,
		/* Prime[267] = */ 1721,
		/* Prime[268] = */ 1723,
		/* Prime[269] = */ 1733,
		/* Prime[270] = */ 1741,
		/* Prime[271] = */ 1747,
		/* Prime[272] = */ 1753,
		/* Prime[273] = */ 1759,
		/* Prime[274] = */ 1777,
		/* Prime[275] = */ 1783,
		/* Prime[276] = */ 1787,
		/* Prime[277] = */ 1789,
		/* Prime[278] = */ 1801,
		/* Prime[279] = */ 1811,
		/* Prime[280] = */ 1823,
		/* Prime[281] = */ 1831,
		/* Prime[282] = */ 1847,
		/* Prime[283] = */ 1861,
		/* Prime[284] = */ 1867,
		/* Prime[285] = */ 1871,
		/* Prime[286] = */ 1873,
		/* Prime[287] = */ 1877,
		/* Prime[288] = */ 1879,
		/* Prime[289] = */ 1889,
		/* Prime[290] = */ 1901,
		/* Prime[291] = */ 1907,
		/* Prime[292] = */ 1913,
		/* Prime[293] = */ 1931,
		/* Prime[294] = */ 1933,
		/* Prime[295] = */ 1949,
		/* Prime[296] = */ 1951,
		/* Prime[297] = */ 1973,
		/* Prime[298] = */ 1979,
		/* Prime[299] = */ 1987,
		/* Prime[300] = */ 1993,
		/* Prime[301] = */ 1997,
		/* Prime[302] = */ 1999,
		/* Prime[303] = */ 2003,
		/* Prime[304] = */ 2011,
		/* Prime[305] = */ 2017,
		/* Prime[306] = */ 2027,
		/* Prime[307] = */ 2029,
		/* Prime[308] = */ 2039,
		/* Prime[309] = */ 2053,
		/* Prime[310] = */ 2063,
		/* Prime[311] = */ 2069,
		/* Prime[312] = */ 2081,
		/* Prime[313] = */ 2083,
		/* Prime[314] = */ 2087,
		/* Prime[315] = */ 2089,
		/* Prime[316] = */ 2099,
		/* Prime[317] = */ 2111,
		/* Prime[318] = */ 2113,
		/* Prime[319] = */ 2129,
		/* Prime[320] = */ 2131,
		/* Prime[321] = */ 2137,
		/* Prime[322] = */ 2141,
		/* Prime[323] = */ 2143,
		/* Prime[324] = */ 2153,
		/* Prime[325] = */ 2161,
		/* Prime[326] = */ 2179,
		/* Prime[327] = */ 2203,
		/* Prime[328] = */ 2207,
		/* Prime[329] = */ 2213,
		/* Prime[330] = */ 2221,
		/* Prime[331] = */ 2237,
		/* Prime[332] = */ 2239,
		/* Prime[333] = */ 2243,
		/* Prime[334] = */ 2251,
		/* Prime[335] = */ 2267,
		/* Prime[336] = */ 2269,
		/* Prime[337] = */ 2273,
		/* Prime[338] = */ 2281,
		/* Prime[339] = */ 2287,
		/* Prime[340] = */ 2293,
		/* Prime[341] = */ 2297,
		/* Prime[342] = */ 2309,
		/* Prime[343] = */ 2311,
		/* Prime[344] = */ 2333,
		/* Prime[345] = */ 2339,
		/* Prime[346] = */ 2341,
		/* Prime[347] = */ 2347,
		/* Prime[348] = */ 2351,
		/* Prime[349] = */ 2357,
		/* Prime[350] = */ 2371,
		/* Prime[351] = */ 2377,
		/* Prime[352] = */ 2381,
		/* Prime[353] = */ 2383,
		/* Prime[354] = */ 2389,
		/* Prime[355] = */ 2393,
		/* Prime[356] = */ 2399,
		/* Prime[357] = */ 2411,
		/* Prime[358] = */ 2417,
		/* Prime[359] = */ 2423,
		/* Prime[360] = */ 2437,
		/* Prime[361] = */ 2441,
		/* Prime[362] = */ 2447,
		/* Prime[363] = */ 2459,
		/* Prime[364] = */ 2467,
		/* Prime[365] = */ 2473,
		/* Prime[366] = */ 2477,
		/* Prime[367] = */ 2503,
		/* Prime[368] = */ 2521,
		/* Prime[369] = */ 2531,
		/* Prime[370] = */ 2539,
		/* Prime[371] = */ 2543,
		/* Prime[372] = */ 2549,
		/* Prime[373] = */ 2551,
		/* Prime[374] = */ 2557,
		/* Prime[375] = */ 2579,
		/* Prime[376] = */ 2591,
		/* Prime[377] = */ 2593,
		/* Prime[378] = */ 2609,
		/* Prime[379] = */ 2617,
		/* Prime[380] = */ 2621,
		/* Prime[381] = */ 2633,
		/* Prime[382] = */ 2647,
		/* Prime[383] = */ 2657,
		/* Prime[384] = */ 2659,
		/* Prime[385] = */ 2663,
		/* Prime[386] = */ 2671,
		/* Prime[387] = */ 2677,
		/* Prime[388] = */ 2683,
		/* Prime[389] = */ 2687,
		/* Prime[390] = */ 2689,
		/* Prime[391] = */ 2693,
		/* Prime[392] = */ 2699,
		/* Prime[393] = */ 2707,
		/* Prime[394] = */ 2711,
		/* Prime[395] = */ 2713,
		/* Prime[396] = */ 2719,
		/* Prime[397] = */ 2729,
		/* Prime[398] = */ 2731,
		/* Prime[399] = */ 2741,
		/* Prime[400] = */ 2749,
		/* Prime[401] = */ 2753,
		/* Prime[402] = */ 2767,
		/* Prime[403] = */ 2777,
		/* Prime[404] = */ 2789,
		/* Prime[405] = */ 2791,
		/* Prime[406] = */ 2797,
		/* Prime[407] = */ 2801,
		/* Prime[408] = */ 2803,
		/* Prime[409] = */ 2819,
		/* Prime[410] = */ 2833,
		/* Prime[411] = */ 2837,
		/* Prime[412] = */ 2843,
		/* Prime[413] = */ 2851,
		/* Prime[414] = */ 2857,
		/* Prime[415] = */ 2861,
		/* Prime[416] = */ 2879,
		/* Prime[417] = */ 2887,
		/* Prime[418] = */ 2897,
		/* Prime[419] = */ 2903,
		/* Prime[420] = */ 2909,
		/* Prime[421] = */ 2917,
		/* Prime[422] = */ 2927,
		/* Prime[423] = */ 2939,
		/* Prime[424] = */ 2953,
		/* Prime[425] = */ 2957,
		/* Prime[426] = */ 2963,
		/* Prime[427] = */ 2969,
		/* Prime[428] = */ 2971,
		/* Prime[429] = */ 2999,
		/* Prime[430] = */ 3001,
		/* Prime[431] = */ 3011,
		/* Prime[432] = */ 3019,
		/* Prime[433] = */ 3023,
		/* Prime[434] = */ 3037,
		/* Prime[435] = */ 3041,
		/* Prime[436] = */ 3049,
		/* Prime[437] = */ 3061,
		/* Prime[438] = */ 3067,
		/* Prime[439] = */ 3079,
		/* Prime[440] = */ 3083,
		/* Prime[441] = */ 3089,
		/* Prime[442] = */ 3109,
		/* Prime[443] = */ 3119,
		/* Prime[444] = */ 3121,
		/* Prime[445] = */ 3137,
		/* Prime[446] = */ 3163,
		/* Prime[447] = */ 3167,
		/* Prime[448] = */ 3169,
		/* Prime[449] = */ 3181,
		/* Prime[450] = */ 3187,
		/* Prime[451] = */ 3191,
		/* Prime[452] = */ 3203,
		/* Prime[453] = */ 3209,
		/* Prime[454] = */ 3217,
		/* Prime[455] = */ 3221,
		/* Prime[456] = */ 3229,
		/* Prime[457] = */ 3251,
		/* Prime[458] = */ 3253,
		/* Prime[459] = */ 3257,
		/* Prime[460] = */ 3259,
		/* Prime[461] = */ 3271,
		/* Prime[462] = */ 3299,
		/* Prime[463] = */ 3301,
		/* Prime[464] = */ 3307,
		/* Prime[465] = */ 3313,
		/* Prime[466] = */ 3319,
		/* Prime[467] = */ 3323,
		/* Prime[468] = */ 3329,
		/* Prime[469] = */ 3331,
		/* Prime[470] = */ 3343,
		/* Prime[471] = */ 3347,
		/* Prime[472] = */ 3359,
		/* Prime[473] = */ 3361,
		/* Prime[474] = */ 3371,
		/* Prime[475] = */ 3373,
		/* Prime[476] = */ 3389,
		/* Prime[477] = */ 3391,
		/* Prime[478] = */ 3407,
		/* Prime[479] = */ 3413,
		/* Prime[480] = */ 3433,
		/* Prime[481] = */ 3449,
		/* Prime[482] = */ 3457,
		/* Prime[483] = */ 3461,
		/* Prime[484] = */ 3463,
		/* Prime[485] = */ 3467,
		/* Prime[486] = */ 3469,
		/* Prime[487] = */ 3491,
		/* Prime[488] = */ 3499,
		/* Prime[489] = */ 3511,
		/* Prime[490] = */ 3517,
		/* Prime[491] = */ 3527,
		/* Prime[492] = */ 3529,
		/* Prime[493] = */ 3533,
		/* Prime[494] = */ 3539,
		/* Prime[495] = */ 3541,
		/* Prime[496] = */ 3547,
		/* Prime[497] = */ 3557,
		/* Prime[498] = */ 3559,
		/* Prime[499] = */ 3571,
		/* Prime[500] = */ 3581,
		/* Prime[501] = */ 3583,
		/* Prime[502] = */ 3593,
		/* Prime[503] = */ 3607,
		/* Prime[504] = */ 3613,
		/* Prime[505] = */ 3617,
		/* Prime[506] = */ 3623,
		/* Prime[507] = */ 3631,
		/* Prime[508] = */ 3637,
		/* Prime[509] = */ 3643,
		/* Prime[510] = */ 3659,
		/* Prime[511] = */ 3671,
		/* Prime[512] = */ 3673,
		/* Prime[513] = */ 3677,
		/* Prime[514] = */ 3691,
		/* Prime[515] = */ 3697,
		/* Prime[516] = */ 3701,
		/* Prime[517] = */ 3709,
		/* Prime[518] = */ 3719,
		/* Prime[519] = */ 3727,
		/* Prime[520] = */ 3733,
		/* Prime[521] = */ 3739,
		/* Prime[522] = */ 3761,
		/* Prime[523] = */ 3767,
		/* Prime[524] = */ 3769,
		/* Prime[525] = */ 3779,
		/* Prime[526] = */ 3793,
		/* Prime[527] = */ 3797,
		/* Prime[528] = */ 3803,
		/* Prime[529] = */ 3821,
		/* Prime[530] = */ 3823,
		/* Prime[531] = */ 3833,
		/* Prime[532] = */ 3847,
		/* Prime[533] = */ 3851,
		/* Prime[534] = */ 3853,
		/* Prime[535] = */ 3863,
		/* Prime[536] = */ 3877,
		/* Prime[537] = */ 3881,
		/* Prime[538] = */ 3889,
		/* Prime[539] = */ 3907,
		/* Prime[540] = */ 3911,
		/* Prime[541] = */ 3917,
		/* Prime[542] = */ 3919,
		/* Prime[543] = */ 3923,
		/* Prime[544] = */ 3929,
		/* Prime[545] = */ 3931,
		/* Prime[546] = */ 3943,
		/* Prime[547] = */ 3947,
		/* Prime[548] = */ 3967,
		/* Prime[549] = */ 3989,
		/* Prime[550] = */ 4001,
		/* Prime[551] = */ 4003,
		/* Prime[552] = */ 4007,
		/* Prime[553] = */ 4013,
		/* Prime[554] = */ 4019,
		/* Prime[555] = */ 4021,
		/* Prime[556] = */ 4027,
		/* Prime[557] = */ 4049,
		/* Prime[558] = */ 4051,
		/* Prime[559] = */ 4057,
		/* Prime[560] = */ 4073,
		/* Prime[561] = */ 4079,
		/* Prime[562] = */ 4091,
		/* Prime[563] = */ 4093,
		/* Prime[564] = */ 4099,
		/* Prime[565] = */ 4111,
		/* Prime[566] = */ 4127,
		/* Prime[567] = */ 4129,
		/* Prime[568] = */ 4133,
		/* Prime[569] = */ 4139,
		/* Prime[570] = */ 4153,
		/* Prime[571] = */ 4157,
		/* Prime[572] = */ 4159,
		/* Prime[573] = */ 4177,
		/* Prime[574] = */ 4201,
		/* Prime[575] = */ 4211,
		/* Prime[576] = */ 4217,
		/* Prime[577] = */ 4219,
		/* Prime[578] = */ 4229,
		/* Prime[579] = */ 4231,
		/* Prime[580] = */ 4241,
		/* Prime[581] = */ 4243,
		/* Prime[582] = */ 4253,
		/* Prime[583] = */ 4259,
		/* Prime[584] = */ 4261,
		/* Prime[585] = */ 4271,
		/* Prime[586] = */ 4273,
		/* Prime[587] = */ 4283,
		/* Prime[588] = */ 4289,
		/* Prime[589] = */ 4297,
		/* Prime[590] = */ 4327,
		/* Prime[591] = */ 4337,
		/* Prime[592] = */ 4339,
		/* Prime[593] = */ 4349,
		/* Prime[594] = */ 4357,
		/* Prime[595] = */ 4363,
		/* Prime[596] = */ 4373,
		/* Prime[597] = */ 4391,
		/* Prime[598] = */ 4397,
		/* Prime[599] = */ 4409,
		/* Prime[600] = */ 4421,
		/* Prime[601] = */ 4423,
		/* Prime[602] = */ 4441,
		/* Prime[603] = */ 4447,
		/* Prime[604] = */ 4451,
		/* Prime[605] = */ 4457,
		/* Prime[606] = */ 4463,
		/* Prime[607] = */ 4481,
		/* Prime[608] = */ 4483,
		/* Prime[609] = */ 4493,
		/* Prime[610] = */ 4507,
		/* Prime[611] = */ 4513,
		/* Prime[612] = */ 4517,
		/* Prime[613] = */ 4519,
		/* Prime[614] = */ 4523,
		/* Prime[615] = */ 4547,
		/* Prime[616] = */ 4549,
		/* Prime[617] = */ 4561,
		/* Prime[618] = */ 4567,
		/* Prime[619] = */ 4583,
		/* Prime[620] = */ 4591,
		/* Prime[621] = */ 4597,
		/* Prime[622] = */ 4603,
		/* Prime[623] = */ 4621,
		/* Prime[624] = */ 4637,
		/* Prime[625] = */ 4639,
		/* Prime[626] = */ 4643,
		/* Prime[627] = */ 4649,
		/* Prime[628] = */ 4651,
		/* Prime[629] = */ 4657,
		/* Prime[630] = */ 4663,
		/* Prime[631] = */ 4673,
		/* Prime[632] = */ 4679,
		/* Prime[633] = */ 4691,
		/* Prime[634] = */ 4703,
		/* Prime[635] = */ 4721,
		/* Prime[636] = */ 4723,
		/* Prime[637] = */ 4729,
		/* Prime[638] = */ 4733,
		/* Prime[639] = */ 4751,
		/* Prime[640] = */ 4759,
		/* Prime[641] = */ 4783,
		/* Prime[642] = */ 4787,
		/* Prime[643] = */ 4789,
		/* Prime[644] = */ 4793,
		/* Prime[645] = */ 4799,
		/* Prime[646] = */ 4801,
		/* Prime[647] = */ 4813,
		/* Prime[648] = */ 4817,
		/* Prime[649] = */ 4831,
		/* Prime[650] = */ 4861,
		/* Prime[651] = */ 4871,
		/* Prime[652] = */ 4877,
		/* Prime[653] = */ 4889,
		/* Prime[654] = */ 4903,
		/* Prime[655] = */ 4909,
		/* Prime[656] = */ 4919,
		/* Prime[657] = */ 4931,
		/* Prime[658] = */ 4933,
		/* Prime[659] = */ 4937,
		/* Prime[660] = */ 4943,
		/* Prime[661] = */ 4951,
		/* Prime[662] = */ 4957,
		/* Prime[663] = */ 4967,
		/* Prime[664] = */ 4969,
		/* Prime[665] = */ 4973,
		/* Prime[666] = */ 4987,
		/* Prime[667] = */ 4993,
		/* Prime[668] = */ 4999,
		/* Prime[669] = */ 5003,
		/* Prime[670] = */ 5009,
		/* Prime[671] = */ 5011,
		/* Prime[672] = */ 5021,
		/* Prime[673] = */ 5023,
		/* Prime[674] = */ 5039,
		/* Prime[675] = */ 5051,
		/* Prime[676] = */ 5059,
		/* Prime[677] = */ 5077,
		/* Prime[678] = */ 5081,
		/* Prime[679] = */ 5087,
		/* Prime[680] = */ 5099,
		/* Prime[681] = */ 5101,
		/* Prime[682] = */ 5107,
		/* Prime[683] = */ 5113,
		/* Prime[684] = */ 5119,
		/* Prime[685] = */ 5147,
		/* Prime[686] = */ 5153,
		/* Prime[687] = */ 5167,
		/* Prime[688] = */ 5171,
		/* Prime[689] = */ 5179,
		/* Prime[690] = */ 5189,
		/* Prime[691] = */ 5197,
		/* Prime[692] = */ 5209,
		/* Prime[693] = */ 5227,
		/* Prime[694] = */ 5231,
		/* Prime[695] = */ 5233,
		/* Prime[696] = */ 5237,
		/* Prime[697] = */ 5261,
		/* Prime[698] = */ 5273,
		/* Prime[699] = */ 5279,
		/* Prime[700] = */ 5281,
		/* Prime[701] = */ 5297,
		/* Prime[702] = */ 5303,
		/* Prime[703] = */ 5309,
		/* Prime[704] = */ 5323,
		/* Prime[705] = */ 5333,
		/* Prime[706] = */ 5347,
		/* Prime[707] = */ 5351,
		/* Prime[708] = */ 5381,
		/* Prime[709] = */ 5387,
		/* Prime[710] = */ 5393,
		/* Prime[711] = */ 5399,
		/* Prime[712] = */ 5407,
		/* Prime[713] = */ 5413,
		/* Prime[714] = */ 5417,
		/* Prime[715] = */ 5419,
		/* Prime[716] = */ 5431,
		/* Prime[717] = */ 5437,
		/* Prime[718] = */ 5441,
		/* Prime[719] = */ 5443,
		/* Prime[720] = */ 5449,
		/* Prime[721] = */ 5471,
		/* Prime[722] = */ 5477,
		/* Prime[723] = */ 5479,
		/* Prime[724] = */ 5483,
		/* Prime[725] = */ 5501,
		/* Prime[726] = */ 5503,
		/* Prime[727] = */ 5507,
		/* Prime[728] = */ 5519,
		/* Prime[729] = */ 5521,
		/* Prime[730] = */ 5527,
		/* Prime[731] = */ 5531,
		/* Prime[732] = */ 5557,
		/* Prime[733] = */ 5563,
		/* Prime[734] = */ 5569,
		/* Prime[735] = */ 5573,
		/* Prime[736] = */ 5581,
		/* Prime[737] = */ 5591,
		/* Prime[738] = */ 5623,
		/* Prime[739] = */ 5639,
		/* Prime[740] = */ 5641,
		/* Prime[741] = */ 5647,
		/* Prime[742] = */ 5651,
		/* Prime[743] = */ 5653,
		/* Prime[744] = */ 5657,
		/* Prime[745] = */ 5659,
		/* Prime[746] = */ 5669,
		/* Prime[747] = */ 5683,
		/* Prime[748] = */ 5689,
		/* Prime[749] = */ 5693,
		/* Prime[750] = */ 5701,
		/* Prime[751] = */ 5711,
		/* Prime[752] = */ 5717,
		/* Prime[753] = */ 5737,
		/* Prime[754] = */ 5741,
		/* Prime[755] = */ 5743,
		/* Prime[756] = */ 5749,
		/* Prime[757] = */ 5779,
		/* Prime[758] = */ 5783,
		/* Prime[759] = */ 5791,
		/* Prime[760] = */ 5801,
		/* Prime[761] = */ 5807,
		/* Prime[762] = */ 5813,
		/* Prime[763] = */ 5821,
		/* Prime[764] = */ 5827,
		/* Prime[765] = */ 5839,
		/* Prime[766] = */ 5843,
		/* Prime[767] = */ 5849,
		/* Prime[768] = */ 5851,
		/* Prime[769] = */ 5857,
		/* Prime[770] = */ 5861,
		/* Prime[771] = */ 5867,
		/* Prime[772] = */ 5869,
		/* Prime[773] = */ 5879,
		/* Prime[774] = */ 5881,
		/* Prime[775] = */ 5897,
		/* Prime[776] = */ 5903,
		/* Prime[777] = */ 5923,
		/* Prime[778] = */ 5927,
		/* Prime[779] = */ 5939,
		/* Prime[780] = */ 5953,
		/* Prime[781] = */ 5981,
		/* Prime[782] = */ 5987,
		/* Prime[783] = */ 6007,
		/* Prime[784] = */ 6011,
		/* Prime[785] = */ 6029,
		/* Prime[786] = */ 6037,
		/* Prime[787] = */ 6043,
		/* Prime[788] = */ 6047,
		/* Prime[789] = */ 6053,
		/* Prime[790] = */ 6067,
		/* Prime[791] = */ 6073,
		/* Prime[792] = */ 6079,
		/* Prime[793] = */ 6089,
		/* Prime[794] = */ 6091,
		/* Prime[795] = */ 6101,
		/* Prime[796] = */ 6113,
		/* Prime[797] = */ 6121,
		/* Prime[798] = */ 6131,
		/* Prime[799] = */ 6133,
		/* Prime[800] = */ 6143,
		/* Prime[801] = */ 6151,
		/* Prime[802] = */ 6163,
		/* Prime[803] = */ 6173,
		/* Prime[804] = */ 6197,
		/* Prime[805] = */ 6199,
		/* Prime[806] = */ 6203,
		/* Prime[807] = */ 6211,
		/* Prime[808] = */ 6217,
		/* Prime[809] = */ 6221,
		/* Prime[810] = */ 6229,
		/* Prime[811] = */ 6247,
		/* Prime[812] = */ 6257,
		/* Prime[813] = */ 6263,
		/* Prime[814] = */ 6269,
		/* Prime[815] = */ 6271,
		/* Prime[816] = */ 6277,
		/* Prime[817] = */ 6287,
		/* Prime[818] = */ 6299,
		/* Prime[819] = */ 6301,
		/* Prime[820] = */ 6311,
		/* Prime[821] = */ 6317,
		/* Prime[822] = */ 6323,
		/* Prime[823] = */ 6329,
		/* Prime[824] = */ 6337,
		/* Prime[825] = */ 6343,
		/* Prime[826] = */ 6353,
		/* Prime[827] = */ 6359,
		/* Prime[828] = */ 6361,
		/* Prime[829] = */ 6367,
		/* Prime[830] = */ 6373,
		/* Prime[831] = */ 6379,
		/* Prime[832] = */ 6389,
		/* Prime[833] = */ 6397,
		/* Prime[834] = */ 6421,
		/* Prime[835] = */ 6427,
		/* Prime[836] = */ 6449,
		/* Prime[837] = */ 6451,
		/* Prime[838] = */ 6469,
		/* Prime[839] = */ 6473,
		/* Prime[840] = */ 6481,
		/* Prime[841] = */ 6491,
		/* Prime[842] = */ 6521,
		/* Prime[843] = */ 6529,
		/* Prime[844] = */ 6547,
		/* Prime[845] = */ 6551,
		/* Prime[846] = */ 6553,
		/* Prime[847] = */ 6563,
		/* Prime[848] = */ 6569,
		/* Prime[849] = */ 6571,
		/* Prime[850] = */ 6577,
		/* Prime[851] = */ 6581,
		/* Prime[852] = */ 6599,
		/* Prime[853] = */ 6607,
		/* Prime[854] = */ 6619,
		/* Prime[855] = */ 6637,
		/* Prime[856] = */ 6653,
		/* Prime[857] = */ 6659,
		/* Prime[858] = */ 6661,
		/* Prime[859] = */ 6673,
		/* Prime[860] = */ 6679,
		/* Prime[861] = */ 6689,
		/* Prime[862] = */ 6691,
		/* Prime[863] = */ 6701,
		/* Prime[864] = */ 6703,
		/* Prime[865] = */ 6709,
		/* Prime[866] = */ 6719,
		/* Prime[867] = */ 6733,
		/* Prime[868] = */ 6737,
		/* Prime[869] = */ 6761,
		/* Prime[870] = */ 6763,
		/* Prime[871] = */ 6779,
		/* Prime[872] = */ 6781,
		/* Prime[873] = */ 6791,
		/* Prime[874] = */ 6793,
		/* Prime[875] = */ 6803,
		/* Prime[876] = */ 6823,
		/* Prime[877] = */ 6827,
		/* Prime[878] = */ 6829,
		/* Prime[879] = */ 6833,
		/* Prime[880] = */ 6841,
		/* Prime[881] = */ 6857,
		/* Prime[882] = */ 6863,
		/* Prime[883] = */ 6869,
		/* Prime[884] = */ 6871,
		/* Prime[885] = */ 6883,
		/* Prime[886] = */ 6899,
		/* Prime[887] = */ 6907,
		/* Prime[888] = */ 6911,
		/* Prime[889] = */ 6917,
		/* Prime[890] = */ 6947,
		/* Prime[891] = */ 6949,
		/* Prime[892] = */ 6959,
		/* Prime[893] = */ 6961,
		/* Prime[894] = */ 6967,
		/* Prime[895] = */ 6971,
		/* Prime[896] = */ 6977,
		/* Prime[897] = */ 6983,
		/* Prime[898] = */ 6991,
		/* Prime[899] = */ 6997,
		/* Prime[900] = */ 7001,
		/* Prime[901] = */ 7013,
		/* Prime[902] = */ 7019,
		/* Prime[903] = */ 7027,
		/* Prime[904] = */ 7039,
		/* Prime[905] = */ 7043,
		/* Prime[906] = */ 7057,
		/* Prime[907] = */ 7069,
		/* Prime[908] = */ 7079,
		/* Prime[909] = */ 7103,
		/* Prime[910] = */ 7109,
		/* Prime[911] = */ 7121,
		/* Prime[912] = */ 7127,
		/* Prime[913] = */ 7129,
		/* Prime[914] = */ 7151,
		/* Prime[915] = */ 7159,
		/* Prime[916] = */ 7177,
		/* Prime[917] = */ 7187,
		/* Prime[918] = */ 7193,
		/* Prime[919] = */ 7207,
		/* Prime[920] = */ 7211,
		/* Prime[921] = */ 7213,
		/* Prime[922] = */ 7219,
		/* Prime[923] = */ 7229,
		/* Prime[924] = */ 7237,
		/* Prime[925] = */ 7243,
		/* Prime[926] = */ 7247,
		/* Prime[927] = */ 7253,
		/* Prime[928] = */ 7283,
		/* Prime[929] = */ 7297,
		/* Prime[930] = */ 7307,
		/* Prime[931] = */ 7309,
		/* Prime[932] = */ 7321,
		/* Prime[933] = */ 7331,
		/* Prime[934] = */ 7333,
		/* Prime[935] = */ 7349,
		/* Prime[936] = */ 7351,
		/* Prime[937] = */ 7369,
		/* Prime[938] = */ 7393,
		/* Prime[939] = */ 7411,
		/* Prime[940] = */ 7417,
		/* Prime[941] = */ 7433,
		/* Prime[942] = */ 7451,
		/* Prime[943] = */ 7457,
		/* Prime[944] = */ 7459,
		/* Prime[945] = */ 7477,
		/* Prime[946] = */ 7481,
		/* Prime[947] = */ 7487,
		/* Prime[948] = */ 7489,
		/* Prime[949] = */ 7499,
		/* Prime[950] = */ 7507,
		/* Prime[951] = */ 7517,
		/* Prime[952] = */ 7523,
		/* Prime[953] = */ 7529,
		/* Prime[954] = */ 7537,
		/* Prime[955] = */ 7541,
		/* Prime[956] = */ 7547,
		/* Prime[957] = */ 7549,
		/* Prime[958] = */ 7559,
		/* Prime[959] = */ 7561,
		/* Prime[960] = */ 7573,
		/* Prime[961] = */ 7577,
		/* Prime[962] = */ 7583,
		/* Prime[963] = */ 7589,
		/* Prime[964] = */ 7591,
		/* Prime[965] = */ 7603,
		/* Prime[966] = */ 7607,
		/* Prime[967] = */ 7621,
		/* Prime[968] = */ 7639,
		/* Prime[969] = */ 7643,
		/* Prime[970] = */ 7649,
		/* Prime[971] = */ 7669,
		/* Prime[972] = */ 7673,
		/* Prime[973] = */ 7681,
		/* Prime[974] = */ 7687,
		/* Prime[975] = */ 7691,
		/* Prime[976] = */ 7699,
		/* Prime[977] = */ 7703,
		/* Prime[978] = */ 7717,
		/* Prime[979] = */ 7723,
		/* Prime[980] = */ 7727,
		/* Prime[981] = */ 7741,
		/* Prime[982] = */ 7753,
		/* Prime[983] = */ 7757,
		/* Prime[984] = */ 7759,
		/* Prime[985] = */ 7789,
		/* Prime[986] = */ 7793,
		/* Prime[987] = */ 7817,
		/* Prime[988] = */ 7823,
		/* Prime[989] = */ 7829,
		/* Prime[990] = */ 7841,
		/* Prime[991] = */ 7853,
		/* Prime[992] = */ 7867,
		/* Prime[993] = */ 7873,
		/* Prime[994] = */ 7877,
		/* Prime[995] = */ 7879,
		/* Prime[996] = */ 7883,
		/* Prime[997] = */ 7901,
		/* Prime[998] = */ 7907,
		/* Prime[999] = */ 7919,
	}
)

func TestSieve(t *testing.T) {
	for j := 0; j < 2; j++ { // one Sieve run should not affect others...
		s := NewSieve()
		for i := 0; i < 1000; i++ {
			want := FirstThousandPrimes[i]
			if got := s.Next(); got != want {
				t.Errorf("Prime[%d]: want %d, got %d", i, want, got)
			}
		}
	}
}

var result uint64

// A becnhmark that times the result of generating the first N primes
func benchmarkSieveN(b *testing.B, n int) {
	var p uint64
	for i := 0; i < b.N; i++ {
		s := NewSieve()
		for j := 0; j < n; j++ {
			p = s.Next()
		}
	}
	result = p
}

func BenchmarkSieve1k(b *testing.B) {
	benchmarkSieveN(b, 1e3)
}

func BenchmarkSieve10k(b *testing.B) {
	benchmarkSieveN(b, 1e4)
}

func BenchmarkSieve100k(b *testing.B) {
	benchmarkSieveN(b, 1e5)
}