Skip to content

Instantly share code, notes, and snippets.

@Maginnovision

Maginnovision/Primes.c

Last active November 12, 2019 23:47
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Maginnovision/2f7bd99afeeed351d421573950fbfdee to your computer and use it in GitHub Desktop.
Save Maginnovision/2f7bd99afeeed351d421573950fbfdee to your computer and use it in GitHub Desktop.
Download ZIP
Raw
Primes.c
/*
* CPrimes.c
*
* Created on: Nov 11, 2019
* Author: Maginnovision
*/
#ifndef CPRIMES_C_
#define CPRIMES_C_
#include <stdio.h>
#define SZ 1000
#define REQ_PRIMES 928290
//Normal countPrimes with provision for printing state and arrays at any point
int countPrimes() {
int primes[SZ], sieve[SZ];
int nSieve = 0;
primes[0] = 2;
sieve[0] = 4;
++nSieve;
int nPrimes = 1, trial = 3, sqr = 2;
while (1) {
while (sqr * sqr <= trial) ++sqr;
--sqr;
for (int i = 0; i < nSieve; ++i) {
if (primes[i] > sqr) goto found_prime;
while (sieve[i] < trial) sieve[i] += primes[i];
if (sieve[i] == trial) goto try_next;
}
break;
found_prime:
if (nSieve < SZ) {
primes[nSieve] = trial;
sieve[nSieve] = trial * trial;
++nSieve;
}
++nPrimes;
//Print state and arrays after 1/4 done
/*if (nPrimes == (REQ_PRIMES)) {
printf("trial: %u, sqr:%u, nSieve: %u\n", trial+1, sqr, nSieve);
printf("int primes[] = {");
for (int i = 0; i < SZ; ++i) printf("%u, ", primes[i]);
printf("};\n");
printf("int sieve[] = {");
for (int i = 0; i < SZ; ++i) printf("%u, ", sieve[i]);
printf("};\n");
}
//Print state and arrays after 1/2 done
if (nPrimes == (REQ_PRIMES * 2)) {
printf("trial: %u, sqr:%u, nSieve: %u\n", trial+1, sqr, nSieve);
printf("int primes[] = {");
for (int i = 0; i < SZ; ++i) printf("%u, ", primes[i]);
printf("};\n");
printf("int sieve[] = {");
for (int i = 0; i < SZ; ++i) printf("%u, ", sieve[i]);
printf("};\n");
}
//Print state and arrays after 3/4 done
if (nPrimes == (REQ_PRIMES * 3)) {
printf("trial: %u, sqr:%u, nSieve: %u\n", trial+1, sqr, nSieve);
printf("int primes[] = {");
for (int i = 0; i < SZ; ++i) printf("%u, ", primes[i]);
printf("};\n");
printf("int sieve[] = {");
for (int i = 0; i < SZ; ++i) printf("%u, ", sieve[i]);
printf("};\n");
}*/
try_next:
++trial;
}
return nPrimes;
}
//First thread takes pointer to prime count
void countPrime0(int *nPrimes0) {
int primes[SZ], sieve[SZ];
int nSieve = 0;
primes[0] = 2;
sieve[0] = 4;
++nSieve;
*nPrimes0 = 1;
int trial = 3, sqr = 2;
while (1) {
while (sqr * sqr <= trial) ++sqr;
--sqr;
for (int i = 0; i < nSieve; ++i) {
if (primes[i] > sqr) goto found_prime;
while (sieve[i] < trial) sieve[i] += primes[i];
if (sieve[i] == trial) goto try_next;
}
break;
found_prime:
if (nSieve < SZ) {
primes[nSieve] = trial;
sieve[nSieve] = trial * trial;
++nSieve;
}
++*nPrimes0;
if (*nPrimes0 == REQ_PRIMES) return;
try_next:
++trial;
}
}
//Second thread takes pointer to prime count
void countPrime1(int *nPrimes1) {
int primes1[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473, 6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, 7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919};
int sieve1[] = {14299964, 14299965, 14299965, 14299964, 14299967, 14299974, 14299975, 14299970, 14299974, 14299987, 14299990, 14299982, 14299980, 14299994, 14299985, 14299983, 14300007, 14299986, 14300011, 14299968, 14299970, 14300027, 14299987, 14299986, 14300031, 14299984, 14300005, 14300015, 14300037, 14300037, 14300073, 14300091, 14300060, 14300042, 14299977, 14300002, 14300031, 14299990, 14300043, 14300007, 14300131, 14300086, 14299979, 14300142, 14300033, 14300140, 14300103, 14300098, 14300092, 14300134, 14300142, 14300087, 14299976, 14299972, 14299994, 14300099, 14300040, 14300128, 14300125, 14300090, 14299990, 14300158, 14300060, 14300091, 14300031, 14300187, 14300193, 14300258, 14300217, 14300275, 14300030, 14300047, 14300155, 14300074, 14300049, 14300071, 14300029, 14300337, 14300061, 14300276, 14300051, 14300107, 14300149, 14300258, 14299986, 14300040, 14300201, 14299987, 14300220, 14300218, 14300007, 14300066, 14300268, 14300375, 14300342, 14300290, 14300355, 14300408, 14300389, 14300253, 14300221, 14300418, 14300200, 14300108, 14300124, 14300368, 14300494, 14300195, 14300526, 14300194, 14300313, 14300064, 14300209, 14300138, 14300353, 14300069, 14300320, 14299994, 14300047, 14300300, 14300074, 14300577, 14300271, 14299971, 14300245, 14300400, 14300530, 14300191, 14300090, 14300097, 14300389, 14300521, 14300542, 14300487, 14300712, 14300324, 14300500, 14300577, 14300571, 14300693, 14300363, 14300178, 14300448, 14300484, 14300250, 14300755, 14300545, 14300759, 14300632, 14300773, 14300362, 14300392, 14300185, 14300214, 14300669, 14299967, 14300559, 14300097, 14300494, 14300377, 14300647, 14300718, 14299996, 14300888, 14300349, 14300684, 14300130, 14299971, 14300557, 14300521, 14300646, 14300126, 14299970, 14300852, 14300796, 14299968, 14300957, 14300158, 14300539, 14300013, 14300572, 14300828, 14300812, 14300492, 14300395, 14300555, 14300951, 14300282, 14301043, 14300024, 14300659, 14300248, 14300252, 14300729, 14300976, 14300491, 14300307, 14300057, 14300967, 14300539, 14300644, 14300527, 14300957, 14301050, 14300981, 14301123, 14300499, 14300318, 14300166, 14300407, 14300722, 14300592, 14300425, 14301194, 14300598, 14301146, 14301079, 14300027, 14300187, 14301168, 14300255, 14300578, 14301350, 14301150, 14299967, 14300003, 14301340, 14300782, 14300701, 14301056, 14300426, 14301118, 14301062, 14300536, 14300569, 14300479, 14300356, 14301447, 14300460, 14300104, 14300970, 14301071, 14300524, 14300368, 14300024, 14300707, 14300442, 14300813, 14301003, 14300822, 14301135, 14300132, 14300693, 14300792, 14300858, 14300627, 14300462, 14301330, 14300832, 14301567, 14300137, 14301193, 14299992, 14300771, 14300619, 14300483, 14300912, 14301510, 14300900, 14300716, 14300574, 14300942, 14300974, 14300670, 14301296, 14301443, 14301361, 14301266, 14301741, 14301467, 14301435, 14300110, 14301321, 14301785, 14301220, 14300053, 14300355, 14300863, 14301069, 14301619, 14301223, 14300593, 14301588, 14300986, 14300334, 14301762, 14300830, 14300304, 14300254, 14300439, 14301768, 14300517, 14300846, 14301420, 14300221, 14300530, 14300485, 14300392, 14301546, 14301198, 14300716, 14300928, 14300632, 14301878, 14300124, 14301294, 14300487, 14302025, 14300784, 14300493, 14301141, 14300804, 14301880, 14300239, 14300226, 14301498, 14300777, 14301876, 14301360, 14300406, 14301019, 14301141, 14300493, 14301368, 14300603, 14300236, 14301507, 14301716, 14301870, 14300611, 14301441, 14301122, 14301946, 14300468, 14301290, 14300646, 14301169, 14300271, 14301133, 14302276, 14301872, 14300032, 14300286, 14300383, 14300554, 14300568, 14300439, 14302052, 14301389, 14300546, 14300316, 14301819, 14300268, 14301544, 14301199, 14301359, 14302198, 14302142, 14301633, 14300150, 14302187, 14301832, 14302439, 14300906, 14301301, 14300555, 14302320, 14300395, 14302538, 14301905, 14300176, 14302456, 14301741, 14299974, 14300102, 14300310, 14300534, 14300534, 14300390, 14300214, 14300102, 14302523, 14302001, 14301081, 14300525, 14300223, 14301940, 14302689, 14302247, 14302538, 14300298, 14301835, 14302623, 14301550, 14301992, 14301084, 14301061, 14301906, 14300906, 14300787, 14300984, 14301317, 14300290, 14300616, 14302142, 14302139, 14299993, 14302198, 14302489, 14300178, 14300644, 14302051, 14301322, 14301174, 14301379, 14300052, 14302401, 14301673, 14302394, 14302231, 14302766, 14302250, 14301003, 14301813, 14301233, 14301823, 14302859, 14300992, 14301421, 14301955, 14302037, 14302070, 14301400, 14300615, 14300422, 14301583, 14303086, 14302172, 14301697, 14301776, 14300069, 14302062, 14301395, 14302513, 14302782, 14301240, 14301241, 14301149, 14300188, 14301487, 14300492, 14300812, 14301165, 14303233, 14302775, 14302221, 14301571, 14302192, 14301384, 14299983, 14301354, 14301731, 14302622, 14301055, 14303153, 14301520, 14301580, 14303238, 14302586, 14300470, 14301878, 14303003, 14301609, 14300852, 14302190, 14301375, 14302687, 14302627, 14300413, 14300303, 14300122, 14301985, 14303037, 14301584, 14301099, 14302099, 14301504, 14302697, 14300062, 14301855, 14302514, 14303336, 14300140, 14301755, 14300254, 14301618, 14299981, 14302509, 14300684, 14302418, 14303031, 14302216, 14302662, 14303530, 14302625, 14299996, 14300664, 14301904, 14303274, 14300499, 14301123, 14301675, 14303083, 14303299, 14303355, 14303515, 14386849, 14417209, 14462809, 14600041, 14615329, 14691889, 14799409, 14830201, 14845609, 14922769, 15031129, 15062161, 15124321, 15264649, 15295921, 15342889, 15358561, 15389929, 15437041, 15452761, 15547249, 15578809, 15737089, 15912121, 16008001, 16024009, 16056049, 16104169, 16152361, 16168441, 16216729, 16394401, 16410601, 16459249, 16589329, 16638241, 16736281, 16752649, 16801801, 16900321, 17032129, 17048641, 17081689, 17131321, 17247409, 17280649, 17297281, 17447329, 17648401, 17732521, 17783089, 17799961, 17884441, 17901361, 17986081, 18003049, 18088009, 18139081, 18156121, 18241441, 18258529, 18344089, 18395521, 18464209, 18722929, 18809569, 18826921, 18913801, 18983449, 19035769, 19123129, 19280881, 19333609, 19439281, 19545241, 19562929, 19722481, 19775809, 19811401, 19864849, 19918369, 20079361, 20097289, 20187049, 20313049, 20367169, 20403289, 20421361, 20457529, 20675209, 20693401, 20802721, 20857489, 21003889, 21077281, 21132409, 21187609, 21353641, 21501769, 21520321, 21557449, 21613201, 21631801, 21687649, 21743569, 21836929, 21893041, 22005481, 22118209, 22287841, 22306729, 22363441, 22401289, 22572001, 22648081, 22877089, 22915369, 22934521, 22972849, 23030401, 23049601, 23164969, 23203489, 23338561, 23629321, 23726641, 23785129, 23902321, 24039409, 24098281, 24196561, 24314761, 24334489, 24373969, 24433249, 24512401, 24571849, 24671089, 24690961, 24730729, 24870169, 24930049, 24990001, 25030009, 25090081, 25110121, 25210441, 25230529, 25391521, 25512601, 25593481, 25775929, 25816561, 25877569, 25999801, 26020201, 26081449, 26142769, 26204161, 26491609, 26553409, 26697889, 26739241, 26822041, 26925721, 27008809, 27133681, 27321529, 27363361, 27384289, 27426169, 27678121, 27804529, 27867841, 27888961, 28058209, 28121809, 28185481, 28334329, 28440889, 28590409, 28633201, 28955161, 29019769, 29084449, 29149201, 29235649, 29300569, 29343889, 29365561, 29495761, 29560969, 29604481, 29626249, 29691601, 29931841, 29997529, 30019441, 30063289, 30261001, 30283009, 30327049, 30459361, 30481441, 30547729, 30591961, 30880249, 30946969, 31013761, 31058329, 31147561, 31259281, 31618129, 31798321, 31820881, 31888609, 31933801, 31956409, 32001649, 32024281, 32137561, 32296489, 32364721, 32410249, 32501401, 32615521, 32684089, 32913169, 32959081, 32982049, 33051001, 33396841, 33443089, 33535681, 33651601, 33721249, 33790969, 33884041, 33953929, 34093921, 34140649, 34210801, 34234201, 34304449, 34351321, 34421689, 34445161, 34562641, 34586161, 34774609, 34845409, 35081929, 35129329, 35271721, 35438209, 35772361, 35844169, 36084049, 36132121, 36348841, 36445369, 36517849, 36566209, 36638809, 36808489, 36881329, 36954241, 37075921, 37100281, 37222201, 37368769, 37466641, 37589161, 37613689, 37736449, 37834801, 37982569, 38105929, 38402809, 38427601, 38477209, 38576521, 38651089, 38700841, 38800441, 39025009, 39150049, 39225169, 39300361, 39325441, 39400729, 39526369, 39677401, 39702601, 39828721, 39904489, 39980329, 40056241, 40157569, 40233649, 40360609, 40436881, 40462321, 40538689, 40615129, 40691641, 40819321, 40921609, 41229241, 41306329, 41589601, 41615401, 41847961, 41899729, 42003361, 42133081, 42523441, 42627841, 42863209, 42915601, 42941809, 43072969, 43151761, 43178041, 43256929, 43309561, 43546801, 43652449, 43811161, 44049769, 44262409, 44342281, 44368921, 44528929, 44609041, 44742721, 44769481, 44903401, 44930209, 45010681, 45144961, 45333289, 45387169, 45711121, 45738169, 45954841, 45981961, 46117681, 46144849, 46280809, 46553329, 46607929, 46635241, 46689889, 46799281, 47018449, 47100769, 47183161, 47210641, 47375689, 47596201, 47706649, 47761921, 47844889, 48260809, 48288601, 48427681, 48455521, 48539089, 48594841, 48678529, 48762289, 48874081, 48958009, 49014001, 49182169, 49266361, 49378729, 49547521, 49603849, 49801249, 49970761, 50112241, 50452609, 50537881, 50708641, 50794129, 50822641, 51136801, 51251281, 51509329, 51652969, 51739249, 51940849, 51998521, 52027369, 52113961, 52258441, 52374169, 52461049, 52519009, 52606009, 53042089, 53246209, 53392249, 53421481, 53597041, 53743561, 53772889, 54007801, 54037201, 54302161, 54656449, 54922921, 55011889, 55249489, 55517401, 55606849, 55636681, 55905529, 55965361, 56055169, 56085121, 56235001, 56355049, 56505289, 56595529, 56685841, 56806369, 56866681, 56957209, 56987401, 57138481, 57168721, 57350329, 57410929, 57501889, 57592921, 57623281, 57805609, 57866449, 58079641, 58354321, 58415449, 58507201, 58813561, 58874929, 58997761, 59089969, 59151481, 59274601, 59336209, 59552089, 59644729, 59706529, 59923081, 60109009, 60171049, 60202081, 60668521, 60730849, 61105489, 61199329, 61293241, 61481281, 61669609, 61889689, 61984129, 62047129, 62078641, 62141689, 62425801, 62520649, 62710561};
int nSieve = 1000;
*nPrimes1 = 0;
int trial = 14299964, sqr = 3781;
while (1) {
while (sqr * sqr <= trial) ++sqr;
--sqr;
for (int i = 0; i < nSieve; ++i) {
if (primes[i] > sqr) goto found_prime;
while (sieve[i] < trial) sieve[i] += primes[i];
if (sieve[i] == trial) goto try_next;
}
break;
found_prime:
if (nSieve < SZ) {
primes[nSieve] = trial;
sieve[nSieve] = trial * trial;
++nSieve;
}
++*nPrimes1;
if (*nPrimes1 == REQ_PRIMES) return;
try_next:
++trial;
}
}
//Third thread takes pointer to prime count
void countPrime2(int *nPrimes2) {
int primes2[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473, 6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, 7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919};
int sieve2[] = {29978018, 29978019, 29978020, 29978018, 29978025, 29978026, 29978021, 29978029, 29978039, 29978025, 29978023, 29978029, 29978052, 29978052, 29978057, 29978019, 29978018, 29978023, 29978078, 29978046, 29978034, 29978051, 29978023, 29978048, 29978044, 29978113, 29978047, 29978083, 29978052, 29978109, 29978096, 29978040, 29978066, 29978130, 29978055, 29978030, 29978051, 29978145, 29978170, 29978132, 29978025, 29978125, 29978023, 29978111, 29978081, 29978156, 29978036, 29978113, 29978074, 29978161, 29978246, 29978248, 29978231, 29978185, 29978022, 29978055, 29978167, 29978020, 29978048, 29978204, 29978190, 29978295, 29978243, 29978223, 29978201, 29978056, 29978339, 29978172, 29978024, 29978053, 29978172, 29978295, 29978028, 29978383, 29978142, 29978176, 29978285, 29978264, 29978359, 29978064, 29978193, 29978147, 29978205, 29978322, 29978432, 29978253, 29978383, 29978286, 29978369, 29978324, 29978131, 29978215, 29978259, 29978496, 29978423, 29978297, 29978064, 29978340, 29978360, 29978433, 29978335, 29978297, 29978061, 29978334, 29978071, 29978035, 29978090, 29978522, 29978153, 29978481, 29978516, 29978152, 29978179, 29978170, 29978179, 29978288, 29978589, 29978098, 29978577, 29978569, 29978333, 29978112, 29978237, 29978236, 29978344, 29978265, 29978647, 29978705, 29978572, 29978234, 29978274, 29978564, 29978418, 29978714, 29978073, 29978696, 29978486, 29978404, 29978358, 29978304, 29978615, 29978815, 29978598, 29978750, 29978298, 29978309, 29978685, 29978717, 29978241, 29978031, 29978491, 29978668, 29978733, 29978826, 29978164, 29978277, 29978699, 29978830, 29978378, 29978378, 29978232, 29978521, 29978934, 29978654, 29978268, 29978551, 29978741, 29978793, 29978399, 29978722, 29978980, 29978602, 29978387, 29978693, 29978267, 29978322, 29978724, 29978555, 29978726, 29979036, 29978373, 29978498, 29978804, 29978816, 29978437, 29978488, 29978046, 29978485, 29978337, 29978946, 29979153, 29978651, 29978771, 29978504, 29978872, 29978897, 29978161, 29978082, 29978361, 29978176, 29978997, 29978543, 29978695, 29978498, 29978049, 29978852, 29978481, 29978578, 29978273, 29978311, 29978858, 29978943, 29978121, 29978659, 29978232, 29978774, 29978257, 29978747, 29978310, 29978082, 29978748, 29979171, 29979293, 29978341, 29978416, 29978991, 29978360, 29978687, 29978946, 29979111, 29978296, 29978073, 29978980, 29978402, 29978845, 29979407, 29978037, 29979440, 29978501, 29978240, 29978732, 29978511, 29978947, 29979346, 29979112, 29979570, 29978277, 29979393, 29978894, 29978854, 29978884, 29978725, 29978585, 29978888, 29979218, 29979023, 29978774, 29979102, 29978381, 29978444, 29978901, 29979328, 29978578, 29979644, 29979202, 29978855, 29979278, 29978099, 29978477, 29979167, 29978279, 29978520, 29978053, 29978637, 29979767, 29979362, 29978712, 29978273, 29979446, 29979294, 29979235, 29978963, 29978657, 29978849, 29978419, 29979033, 29979238, 29979444, 29979445, 29978430, 29978770, 29978040, 29978623, 29978775, 29978897, 29979518, 29979066, 29979735, 29979871, 29979856, 29978706, 29978964, 29979003, 29978901, 29979988, 29978671, 29979330, 29978475, 29979417, 29979959, 29979516, 29979810, 29978886, 29978536, 29979755, 29979239, 29980017, 29978311, 29979244, 29978449, 29978908, 29979973, 29978282, 29978427, 29978372, 29979553, 29978682, 29978424, 29979888, 29979511, 29979058, 29978037, 29980210, 29979938, 29978818, 29978808, 29978028, 29978597, 29979183, 29980283, 29978682, 29978147, 29980056, 29978292, 29979050, 29978963, 29978846, 29978231, 29979952, 29978683, 29978924, 29978724, 29979171, 29978140, 29979561, 29979504, 29980303, 29978374, 29978051, 29979779, 29979974, 29980362, 29978197, 29980128, 29978984, 29980179, 29979131, 29978431, 29979732, 29979695, 29980512, 29979427, 29978789, 29979352, 29978268, 29978296, 29980461, 29980266, 29980019, 29980352, 29978998, 29979338, 29979922, 29978931, 29980225, 29980054, 29979304, 29979723, 29979842, 29978859, 29979661, 29978476, 29980492, 29980025, 29978238, 29978650, 29979694, 29978065, 29978187, 29978317, 29980594, 29980170, 29980445, 29980492, 29978961, 29978131, 29978246, 29979103, 29978085, 29980065, 29978806, 29978579, 29979435, 29978265, 29978501, 29980419, 29979027, 29978608, 29978156, 29979281, 29980154, 29980926, 29978334, 29980739, 29978856, 29978066, 29979634, 29980962, 29980361, 29981003, 29979990, 29980527, 29978670, 29979091, 29978227, 29978178, 29980817, 29979434, 29979925, 29980223, 29979092, 29978745, 29980087, 29979828, 29980326, 29980309, 29978914, 29978822, 29978740, 29980925, 29980109, 29979445, 29980080, 29978478, 29979223, 29981068, 29978036, 29980722, 29979648, 29980685, 29979541, 29978715, 29981312, 29979682, 29981262, 29979337, 29980527, 29980106, 29980974, 29979000, 29980024, 29979079, 29979075, 29980120, 29978303, 29979224, 29979094, 29979831, 29978193, 29979792, 29980389, 29978708, 29979104, 29979182, 29979191, 29979149, 29979098, 29980708, 29979432, 29980429, 29978908, 29979500, 29978855, 29981038, 29978869, 29978106, 29979244, 29978396, 29981016, 29978545, 29980132, 29978961, 29979992, 29981384, 29980674, 29981313, 29980325, 29981167, 29979791, 29978247, 29978187, 29981057, 29979026, 29978581, 29978302, 29978973, 29978100, 29979847, 29978859, 29979988, 29979723, 29979302, 29978931, 29981553, 29978626, 29978807, 29979872, 29981112, 29979049, 29979566, 29979966, 29981726, 29979671, 29980035, 29980193, 29980743, 29980841, 29980725, 29980301, 29978411, 29981726, 29980718, 29980350, 29979566, 29978270, 29981737, 29978629, 29981412, 29978619, 29981324, 29979493, 29978467, 29980374, 29981123, 29981740, 29980576, 29981015, 29978796, 29981451, 29981230, 29981353, 29980650, 29978848, 29981225, 29980086, 29981523, 29978528, 29980669, 29980782, 29978777, 29980507, 29980284, 29978072, 29978329, 29978336, 29978109, 29978653, 29980214, 29979381, 29980866, 29979629, 29981038, 29979397, 29979101, 29980396, 29978149, 29979368, 29981000, 29980110, 29980169, 29981783, 29981681, 29978151, 29982006, 29980517, 29978173, 29981288, 29981748, 29978746, 29981200, 29978801, 29979094, 29981191, 29981674, 29981936, 29982239, 29982434, 29982371, 29982304, 29981789, 29980564, 29979859, 29979329, 29979046, 29978444, 29978371, 29982459, 29979453, 29982355, 29981986, 29979230, 29981634, 29979339, 29981048, 29978205, 29981857, 29979851, 29981401, 29980346, 29981766, 29978427, 29981968, 29978353, 29980181, 29981625, 29978350, 29981604, 29981860, 29978822, 29978810, 29981700, 29979844, 29980981, 29979140, 29980215, 29979353, 29982245, 29980177, 29981008, 29981186, 29982648, 29981005, 29978919, 29979348, 29981845, 29979263, 29981305, 29980480, 29982774, 29982401, 29979295, 29978305, 29979936, 29980812, 29982946, 29982217, 29981844, 29982965, 29979003, 29982979, 29978865, 29980813, 29980391, 29982287, 29982050, 29982736, 29979634, 29979685, 29982981, 29982778, 29982120, 29978577, 29978090, 29982632, 29981983, 29981275, 29980154, 29978934, 29981458, 29981231, 29982042, 29981493, 29983004, 29982072, 29978861, 29979857, 29981825, 29982439, 29982278, 29979441, 29980237, 29981020, 29983162, 29979923, 29979136, 29982126, 29980629, 29981653, 29982932, 29978655, 29979687, 29980647, 29981815, 29982607, 29983095, 29983327, 29979120, 29979618, 29979910, 29980044, 29980398, 29981080, 29997529, 30019441, 30063289, 30261001, 30283009, 30327049, 30459361, 30481441, 30547729, 30591961, 30880249, 30946969, 31013761, 31058329, 31147561, 31259281, 31618129, 31798321, 31820881, 31888609, 31933801, 31956409, 32001649, 32024281, 32137561, 32296489, 32364721, 32410249, 32501401, 32615521, 32684089, 32913169, 32959081, 32982049, 33051001, 33396841, 33443089, 33535681, 33651601, 33721249, 33790969, 33884041, 33953929, 34093921, 34140649, 34210801, 34234201, 34304449, 34351321, 34421689, 34445161, 34562641, 34586161, 34774609, 34845409, 35081929, 35129329, 35271721, 35438209, 35772361, 35844169, 36084049, 36132121, 36348841, 36445369, 36517849, 36566209, 36638809, 36808489, 36881329, 36954241, 37075921, 37100281, 37222201, 37368769, 37466641, 37589161, 37613689, 37736449, 37834801, 37982569, 38105929, 38402809, 38427601, 38477209, 38576521, 38651089, 38700841, 38800441, 39025009, 39150049, 39225169, 39300361, 39325441, 39400729, 39526369, 39677401, 39702601, 39828721, 39904489, 39980329, 40056241, 40157569, 40233649, 40360609, 40436881, 40462321, 40538689, 40615129, 40691641, 40819321, 40921609, 41229241, 41306329, 41589601, 41615401, 41847961, 41899729, 42003361, 42133081, 42523441, 42627841, 42863209, 42915601, 42941809, 43072969, 43151761, 43178041, 43256929, 43309561, 43546801, 43652449, 43811161, 44049769, 44262409, 44342281, 44368921, 44528929, 44609041, 44742721, 44769481, 44903401, 44930209, 45010681, 45144961, 45333289, 45387169, 45711121, 45738169, 45954841, 45981961, 46117681, 46144849, 46280809, 46553329, 46607929, 46635241, 46689889, 46799281, 47018449, 47100769, 47183161, 47210641, 47375689, 47596201, 47706649, 47761921, 47844889, 48260809, 48288601, 48427681, 48455521, 48539089, 48594841, 48678529, 48762289, 48874081, 48958009, 49014001, 49182169, 49266361, 49378729, 49547521, 49603849, 49801249, 49970761, 50112241, 50452609, 50537881, 50708641, 50794129, 50822641, 51136801, 51251281, 51509329, 51652969, 51739249, 51940849, 51998521, 52027369, 52113961, 52258441, 52374169, 52461049, 52519009, 52606009, 53042089, 53246209, 53392249, 53421481, 53597041, 53743561, 53772889, 54007801, 54037201, 54302161, 54656449, 54922921, 55011889, 55249489, 55517401, 55606849, 55636681, 55905529, 55965361, 56055169, 56085121, 56235001, 56355049, 56505289, 56595529, 56685841, 56806369, 56866681, 56957209, 56987401, 57138481, 57168721, 57350329, 57410929, 57501889, 57592921, 57623281, 57805609, 57866449, 58079641, 58354321, 58415449, 58507201, 58813561, 58874929, 58997761, 59089969, 59151481, 59274601, 59336209, 59552089, 59644729, 59706529, 59923081, 60109009, 60171049, 60202081, 60668521, 60730849, 61105489, 61199329, 61293241, 61481281, 61669609, 61889689, 61984129, 62047129, 62078641, 62141689, 62425801, 62520649, 62710561};
int nSieve = 1000;
*nPrimes2 = 0;
int trial = 29978018, sqr = 5475;
while (1) {
while (sqr * sqr <= trial) ++sqr;
--sqr;
for (int i = 0; i < nSieve; ++i) {
if (primes[i] > sqr) goto found_prime;
while (sieve[i] < trial) sieve[i] += primes[i];
if (sieve[i] == trial) goto try_next;
}
break;
found_prime:
if (nSieve < SZ) {
primes[nSieve] = trial;
sieve[nSieve] = trial * trial;
++nSieve;
}
++*nPrimes2;
if (*nPrimes2 == REQ_PRIMES) return;
try_next:
++trial;
}
}
////Fourth thread takes pointer to prime count
void countPrime3(int *nPrimes3) {
int primes3[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473, 6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, 7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919};
int sieve3[] = {46173774, 46173774, 46173775, 46173778, 46173776, 46173777, 46173785, 46173781, 46173788, 46173800, 46173787, 46173780, 46173790, 46173787, 46173787, 46173812, 46173813, 46173828, 46173787, 46173785, 46173814, 46173841, 46173813, 46173823, 46173843, 46173867, 46173870, 46173817, 46173817, 46173834, 46173898, 46173832, 46173795, 46173854, 46173908, 46173837, 46173857, 46173825, 46173830, 46173873, 46173945, 46173824, 46173868, 46173899, 46173845, 46173970, 46173974, 46173934, 46173843, 46173957, 46173843, 46173844, 46173913, 46173960, 46173905, 46173858, 46173850, 46173793, 46173961, 46173920, 46173997, 46173870, 46174028, 46173859, 46174073, 46173903, 46173838, 46174055, 46173902, 46174096, 46173812, 46173862, 46174105, 46174043, 46173949, 46174097, 46173911, 46173879, 46173947, 46174055, 46173800, 46174017, 46173892, 46173821, 46174020, 46173890, 46173813, 46173909, 46174221, 46174064, 46174158, 46174163, 46173931, 46174131, 46173967, 46173891, 46173935, 46174146, 46174101, 46173809, 46173911, 46174186, 46173882, 46173781, 46173915, 46173848, 46174007, 46173945, 46173915, 46174229, 46173883, 46174225, 46173812, 46174305, 46174056, 46173794, 46173830, 46173802, 46174283, 46174153, 46174155, 46173857, 46174108, 46174215, 46174002, 46174169, 46174334, 46174180, 46173951, 46173869, 46174198, 46174478, 46174484, 46173972, 46174436, 46173836, 46174382, 46174077, 46174195, 46174484, 46174285, 46173861, 46174415, 46173891, 46174471, 46174365, 46174596, 46174303, 46173827, 46173952, 46174050, 46174091, 46173836, 46174559, 46174463, 46174035, 46174236, 46174087, 46174423, 46173929, 46173826, 46173803, 46174250, 46173963, 46173997, 46174459, 46174654, 46174061, 46173858, 46174566, 46173947, 46174725, 46174366, 46174067, 46174199, 46173833, 46174634, 46174720, 46174594, 46174386, 46174673, 46174393, 46173785, 46173827, 46173786, 46174324, 46174546, 46174391, 46173842, 46174667, 46174191, 46174589, 46174872, 46174738, 46174300, 46173872, 46174847, 46174058, 46174197, 46174365, 46174759, 46174810, 46174736, 46174281, 46173825, 46175043, 46174458, 46173887, 46174558, 46173906, 46174497, 46173791, 46174411, 46175003, 46174233, 46174234, 46174292, 46174647, 46174526, 46173990, 46175116, 46173995, 46174339, 46174927, 46174866, 46173848, 46174126, 46174632, 46175217, 46175173, 46174887, 46174432, 46174690, 46174618, 46174688, 46174324, 46173890, 46174011, 46175196, 46174649, 46174314, 46174960, 46174275, 46174141, 46173796, 46174462, 46174789, 46174832, 46174697, 46174527, 46174061, 46174441, 46173931, 46175082, 46175351, 46173880, 46174185, 46174260, 46174859, 46173962, 46174858, 46174233, 46174554, 46174882, 46175370, 46175422, 46175471, 46174430, 46174677, 46174052, 46174802, 46174957, 46174020, 46175509, 46175345, 46174351, 46174293, 46174090, 46174038, 46175067, 46174767, 46174158, 46175000, 46175132, 46174644, 46174409, 46175069, 46174200, 46174546, 46174716, 46175290, 46174191, 46174081, 46174072, 46175504, 46175708, 46174317, 46174119, 46174028, 46173906, 46173824, 46174634, 46174901, 46175159, 46174571, 46175181, 46175060, 46173953, 46175194, 46174023, 46174066, 46173873, 46175309, 46173861, 46174875, 46175256, 46173802, 46173903, 46175389, 46175881, 46174508, 46174159, 46174947, 46175221, 46175391, 46174087, 46175189, 46174880, 46174854, 46174245, 46174590, 46173917, 46174897, 46174398, 46174763, 46174256, 46174150, 46175995, 46174283, 46174530, 46174141, 46174294, 46175382, 46173780, 46174736, 46174199, 46173884, 46174878, 46175991, 46175987, 46175225, 46175602, 46174733, 46175391, 46174592, 46175328, 46175952, 46175472, 46174368, 46175111, 46173839, 46173956, 46174890, 46175102, 46174839, 46175856, 46176234, 46175344, 46174636, 46175564, 46174254, 46175794, 46175135, 46175651, 46174306, 46174416, 46174211, 46176144, 46174082, 46174348, 46174157, 46174921, 46174268, 46176003, 46176194, 46176420, 46176248, 46175573, 46174430, 46176095, 46175508, 46174178, 46174492, 46176006, 46176463, 46175260, 46174058, 46174680, 46175748, 46174886, 46174953, 46176069, 46175696, 46175956, 46174684, 46174304, 46175673, 46174485, 46173819, 46175220, 46175067, 46175012, 46176006, 46174796, 46174834, 46176540, 46176281, 46174678, 46175283, 46175118, 46174557, 46176110, 46176352, 46174629, 46176061, 46176512, 46175392, 46173888, 46175282, 46175603, 46176387, 46176696, 46175605, 46176325, 46174548, 46174544, 46174056, 46175185, 46176752, 46175763, 46174091, 46174372, 46174868, 46176795, 46175195, 46176640, 46176637, 46174860, 46175499, 46175396, 46176443, 46176961, 46174448, 46174301, 46176818, 46176256, 46174700, 46173953, 46176335, 46174489, 46176771, 46176707, 46176103, 46174388, 46175641, 46176594, 46173928, 46176408, 46176559, 46174322, 46176859, 46175212, 46176173, 46176779, 46175958, 46176370, 46175125, 46175247, 46175071, 46174477, 46173850, 46175212, 46175149, 46176662, 46175642, 46176973, 46175859, 46175457, 46176303, 46176672, 46174693, 46175484, 46176965, 46176310, 46176872, 46174640, 46174846, 46176974, 46174466, 46176601, 46176995, 46174121, 46177236, 46176814, 46174140, 46174622, 46175135, 46175427, 46175352, 46175025, 46176580, 46173838, 46176956, 46175766, 46174410, 46175530, 46177377, 46177050, 46175104, 46173803, 46177210, 46176650, 46173797, 46175886, 46174019, 46175601, 46175982, 46175317, 46176026, 46176785, 46174194, 46176151, 46175541, 46177341, 46174352, 46174439, 46175070, 46176138, 46174097, 46176833, 46177177, 46177513, 46177577, 46177633, 46177537, 46177457, 46176473, 46175953, 46175880, 46176664, 46175541, 46174605, 46176668, 46177591, 46174291, 46177164, 46177609, 46174796, 46177349, 46176774, 46175601, 46174280, 46175117, 46177226, 46175235, 46174752, 46177003, 46174607, 46173876, 46174684, 46177207, 46175956, 46177377, 46176735, 46177392, 46177826, 46176150, 46176955, 46176451, 46177134, 46176008, 46176569, 46174821, 46176078, 46176457, 46173781, 46174038, 46175023, 46175374, 46175562, 46177744, 46176039, 46175638, 46177682, 46175486, 46177992, 46174507, 46175756, 46177294, 46175457, 46177345, 46176120, 46177518, 46177648, 46174674, 46174520, 46174198, 46176705, 46174900, 46174561, 46174215, 46177016, 46177291, 46175142, 46175307, 46174785, 46176899, 46175564, 46176937, 46178308, 46176278, 46176865, 46177296, 46177653, 46175246, 46176606, 46174635, 46173868, 46175128, 46174155, 46177689, 46173913, 46177051, 46178204, 46174054, 46176101, 46176771, 46173956, 46175148, 46174969, 46176577, 46175082, 46175402, 46175538, 46175762, 46175978, 46176018, 46175922, 46175762, 46174698, 46174639, 46177080, 46175436, 46176605, 46176454, 46174054, 46174653, 46173884, 46177813, 46175761, 46177506, 46177977, 46174455, 46178199, 46176917, 46174305, 46174633, 46175264, 46175763, 46177690, 46177971, 46176365, 46178137, 46176439, 46177396, 46176242, 46178552, 46175315, 46176128, 46174699, 46176544, 46174252, 46177494, 46175503, 46178499, 46178884, 46176033, 46177479, 46177030, 46175964, 46176911, 46175345, 46177785, 46175318, 46174037, 46175992, 46174629, 46175797, 46175661, 46175413, 46177064, 46173949, 46178524, 46177682, 46177025, 46178447, 46176692, 46173779, 46174361, 46177364, 46174866, 46177647, 46175780, 46178303, 46174508, 46175299, 46174362, 46176441, 46177767, 46178412, 46174826, 46175240, 46176587, 46177012, 46177826, 46175394, 46175673, 46176195, 46177473, 46177644, 46178085, 46178319, 46178670, 46178463, 46178148, 46177878, 46177194, 46176069, 46176076, 46177771, 46177226, 46175519, 46174321, 46179357, 46178091, 46177440, 46174005, 46174375, 46177613, 46175923, 46178100, 46179146, 46176209, 46177113, 46174863, 46179463, 46175968, 46174210, 46177255, 46177434, 46175960, 46177264, 46178472, 46177993, 46178975, 46174812, 46177229, 46177855, 46176092, 46176588, 46178819, 46179157, 46177292, 46179545, 46177612, 46179407, 46179169, 46175708, 46177257, 46175725, 46177421, 46179301, 46177731, 46175809, 46176502, 46176111, 46177013, 46174563, 46174892, 46178337, 46175937, 46179092, 46176084, 46178976, 46175871, 46178469, 46177602, 46176824, 46178692, 46175357, 46176931, 46175557, 46179359, 46174040, 46173847, 46176351, 46175132, 46178785, 46179876, 46178483, 46175577, 46177824, 46176660, 46177099, 46177454, 46179644, 46179889, 46178015, 46177969, 46180029, 46177587, 46177270, 46176869, 46176384, 46177719, 46177040, 46179957, 46179058, 46174499, 46179851, 46178758, 46177581, 46179692, 46179943, 46179832, 46177995, 46174840, 46176258, 46175722, 46178382, 46177125, 46176974, 46175201, 46179617, 46175991, 46177999, 46178991, 46177268, 46180070, 46174417, 46177117, 46178877, 46179802, 46176323, 46174144, 46180246, 46178473, 46180165, 46174052, 46177160, 46178606, 46174167, 46174591, 46176591, 46176967, 46178047, 46179687, 46174914, 46175398, 46177630, 46177764, 46178548, 46178610, 46178800, 46178814, 46280809, 46553329, 46607929, 46635241, 46689889, 46799281, 47018449, 47100769, 47183161, 47210641, 47375689, 47596201, 47706649, 47761921, 47844889, 48260809, 48288601, 48427681, 48455521, 48539089, 48594841, 48678529, 48762289, 48874081, 48958009, 49014001, 49182169, 49266361, 49378729, 49547521, 49603849, 49801249, 49970761, 50112241, 50452609, 50537881, 50708641, 50794129, 50822641, 51136801, 51251281, 51509329, 51652969, 51739249, 51940849, 51998521, 52027369, 52113961, 52258441, 52374169, 52461049, 52519009, 52606009, 53042089, 53246209, 53392249, 53421481, 53597041, 53743561, 53772889, 54007801, 54037201, 54302161, 54656449, 54922921, 55011889, 55249489, 55517401, 55606849, 55636681, 55905529, 55965361, 56055169, 56085121, 56235001, 56355049, 56505289, 56595529, 56685841, 56806369, 56866681, 56957209, 56987401, 57138481, 57168721, 57350329, 57410929, 57501889, 57592921, 57623281, 57805609, 57866449, 58079641, 58354321, 58415449, 58507201, 58813561, 58874929, 58997761, 59089969, 59151481, 59274601, 59336209, 59552089, 59644729, 59706529, 59923081, 60109009, 60171049, 60202081, 60668521, 60730849, 61105489, 61199329, 61293241, 61481281, 61669609, 61889689, 61984129, 62047129, 62078641, 62141689, 62425801, 62520649, 62710561};
int nSieve = 1000;
*nPrimes3 = 0;
int trial = 46173774, sqr = 6795;
while (1) {
while (sqr * sqr <= trial) ++sqr;
--sqr;
for (int i = 0; i < nSieve; ++i) {
if (primes[i] > sqr) goto found_prime;
while (sieve[i] < trial) sieve[i] += primes[i];
if (sieve[i] == trial) goto try_next;
}
break;
found_prime:
if (nSieve < SZ) {
primes[nSieve] = trial;
sieve[nSieve] = trial * trial;
++nSieve;
}
++*nPrimes3;
if (*nPrimes3 == REQ_PRIMES) return;
try_next:
++trial;
}
}
#endif /* CPRIMES_C_ */
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment