/*
Another version of the sieve of Eratosthenes, ~30% faster than before.
BitArrays are replaced by int arrays.
"isPrime" was useful for a few record times at Project Euler.
Example: isP[0] = 0x64b4cb6e (each byte represents 8 odd numbers)
hex: 6 4 b 4 c b 6 e
bits: 0 1 1 0 0 1 0 0 1 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 1 0 1 1 1 0
primes: 6 5 5 4 4 4 3 3 2 2 1 1 1 1 0 0 0
1 9 3 7 3 1 7 1 9 3 9 7 3 1 7 5 3
Results:
time (in seconds) i7@3G6Hz faster ? scroll down
n x p isP? x = composites
1e9 1.89 2.29 2.48 p = primes
2e9 4.16 4.94 5.31 isP? = isPrime[i], i odd, 1 <= i <= n < 2^32 ~ 4e9
4e9 9.02 10.54 11.31 = (isP[i >> 6] & 1 << (i << 26 >> 27)) != 0
= (isP[i >> 6] & 1 << (i >> 1)) != 0
*/
using System;
using sw = System.Diagnostics.Stopwatch;
class isPrime
{
static sw sw = new sw();
static void Main()
{
test(1000000000);
Console.Read();
}
static void test(uint n)
{
int[] isP;
sw.Start();
isP = buildIsPrime(n);
sw.Stop();
if (n > 0) n -= 1 - (n & 1);
for (int i = 0; i < 10 && n > 1; n -= 2)
if ((isP[n >> 6] & 1 << (int)(n >> 1)) != 0)
{ Console.WriteLine(n); i++; }
}
static int[] buildIsPrime(uint n)
{
int y, d, e, q, r, s, i, j, u; int[] x, isP;
y = (int)(n / 3); x = new int[(y >> 5) + 1];
d = 8; e = 0; q = 3; r = 1; s = 7; i = 0; j = 10;
while (s < y)
{
if ((x[i >> 5] & 1 << i++) == 0)
{
int k = s, m = s + q;
for (; m < y; k += j, m += j)
{
x[k >> 5] |= 1 << k;
x[m >> 5] |= 1 << m;
}
for (; k < y; k += j)
x[k >> 5] |= 1 << k;
}
e += 8; s += e; r += 8; j += 4;
if ((x[i >> 5] & 1 << i++) == 0 && s < y)
{
int k = s, m = s + r;
for (; m < y; k += j, m += j)
{
x[k >> 5] |= 1 << k;
x[m >> 5] |= 1 << m;
}
for (; k < y; k += j)
x[k >> 5] |= 1 << k;
}
d += 16; s += d; q += 4; j += 8;
}
Console.WriteLine(sw.Elapsed + " x");
i = 0; y -= 2; d = y >> 5 << 5; u = 2; n >>= 1;
isP = new int[(n >> 5) + 1]; isP[0] = 2;
while (i < d)
{
q = x[i >> 5];
for (e = 16; e > 0; e--)
{
if ((q & 1 << i++) == 0) isP[u >> 5] |= 1 << u; u += 1;
if ((q & 1 << i++) == 0) isP[u >> 5] |= 1 << u; u += 2;
}
}
while (i < y)
{
if ((x[i >> 5] & 1 << i++) == 0) isP[u >> 5] |= 1 << u; u += 1;
if ((x[i >> 5] & 1 << i++) == 0) isP[u >> 5] |= 1 << u; u += 2;
}
if (u - 3 <= n - 3 && ((x[i >> 5] & 1 << i++) == 0)) isP[u >> 5] |= 1 << u; u += 1;
if (u - 3 <= n - 3 && ((x[i >> 5] & 1 << i++) == 0)) isP[u >> 5] |= 1 << u;
Console.WriteLine(sw.Elapsed + " p");
return isP;
}
}
/*
With an unrolled loop.
*/
using System;
using sw = System.Diagnostics.Stopwatch;
class Eratosthenes
{
static sw sw = new sw();
static void Main()
{
test(1000000000);
Console.Read();
}
static void test(uint n)
{
uint pi_n; uint[] p;
sw.Start();
p = getPrimes(n);
sw.Stop();
pi_n = p[p.Length - 1];
Console.WriteLine("pi(" + n + ") = " + pi_n);
if (pi_n > 0)
Console.Write("largest prime = " + p[pi_n - 1]);
}
static uint[] getPrimes(uint n)
{
int c, y, d, e, q, r, s, i, j; uint u; double logN; int[] x; uint[] p;
if (n < 3) return n < 2 ? new uint[] { 0 } : new uint[] { 2, 1 };
logN = Math.Log(n);
c = (int)(n / logN * (1 + 1.2762 / logN));
p = new uint[c + 1]; p[0] = 2; p[1] = 3;
y = (int)(n / 3); x = new int[(y >> 5) + 1];
d = 8; e = 0; q = 3; r = 1; s = 7; i = 0; j = 10;
while (s < y)
{
if ((x[i >> 5] & 1 << i++) == 0)
{
int k = s, m = s + q;
for (; m < y; k += j, m += j) { x[k >> 5] |= 1 << k; x[m >> 5] |= 1 << m; }
for (; k < y; k += j) x[k >> 5] |= 1 << k;
}
e += 8; s += e; r += 8; j += 4;
if ((x[i >> 5] & 1 << i++) == 0 && s < y)
{
int k = s, m = s + r;
for (; m < y; k += j, m += j) { x[k >> 5] |= 1 << k; x[m >> 5] |= 1 << m; }
for (; k < y; k += j) x[k >> 5] |= 1 << k;
}
d += 16; s += d; q += 4; j += 8;
}
Console.WriteLine(sw.Elapsed + " x");
j = 2; y -= 2; d = y >> 5; u = 5;
for (i = 0; i < d; i++)
{
q = x[i];
if ((q & 1) == 0) p[j++] = u; u += 2; if ((q & 2) == 0) p[j++] = u; u += 4; q >>= 2;
if ((q & 1) == 0) p[j++] = u; u += 2; if ((q & 2) == 0) p[j++] = u; u += 4; q >>= 2;
if ((q & 1) == 0) p[j++] = u; u += 2; if ((q & 2) == 0) p[j++] = u; u += 4; q >>= 2;
if ((q & 1) == 0) p[j++] = u; u += 2; if ((q & 2) == 0) p[j++] = u; u += 4; q >>= 2;
if ((q & 1) == 0) p[j++] = u; u += 2; if ((q & 2) == 0) p[j++] = u; u += 4; q >>= 2;
if ((q & 1) == 0) p[j++] = u; u += 2; if ((q & 2) == 0) p[j++] = u; u += 4; q >>= 2;
if ((q & 1) == 0) p[j++] = u; u += 2; if ((q & 2) == 0) p[j++] = u; u += 4; q >>= 2;
if ((q & 1) == 0) p[j++] = u; u += 2; if ((q & 2) == 0) p[j++] = u; u += 4; q >>= 2;
if ((q & 1) == 0) p[j++] = u; u += 2; if ((q & 2) == 0) p[j++] = u; u += 4; q >>= 2;
if ((q & 1) == 0) p[j++] = u; u += 2; if ((q & 2) == 0) p[j++] = u; u += 4; q >>= 2;
if ((q & 1) == 0) p[j++] = u; u += 2; if ((q & 2) == 0) p[j++] = u; u += 4; q >>= 2;
if ((q & 1) == 0) p[j++] = u; u += 2; if ((q & 2) == 0) p[j++] = u; u += 4; q >>= 2;
if ((q & 1) == 0) p[j++] = u; u += 2; if ((q & 2) == 0) p[j++] = u; u += 4; q >>= 2;
if ((q & 1) == 0) p[j++] = u; u += 2; if ((q & 2) == 0) p[j++] = u; u += 4; q >>= 2;
if ((q & 1) == 0) p[j++] = u; u += 2; if ((q & 2) == 0) p[j++] = u; u += 4; q >>= 2;
if ((q & 1) == 0) p[j++] = u; u += 2; if ((q & 2) == 0) p[j++] = u; u += 4;
}
i <<= 5;
while (i < y)
{
if ((x[i >> 5] & 1 << i++) == 0) p[j++] = u; u += 2;
if ((x[i >> 5] & 1 << i++) == 0) p[j++] = u; u += 4;
}
if (u - 3 <= n - 3 && ((x[i >> 5] & 1 << i++) == 0)) p[j++] = u; u += 2;
if (u - 3 <= n - 3 && ((x[i >> 5] & 1 << i++) == 0)) p[j++] = u;
p[c] = (uint)j;
Console.WriteLine(sw.Elapsed + " p");
return p;
}
}
// for (i = 0; i < d; i++)
// {
// q = x[i];
// for (e = 16; e > 0; e--)
// {
// if ((q & 1) == 0) p[j++] = u; u += 2;
// if ((q & 2) == 0) p[j++] = u; u += 4; q >>= 2;
// }
// }
/*****************************************************
"isPrime" as fast as Eratosthenes, ie isP(1e9) 2.29 s.
*/
using System;
using sw = System.Diagnostics.Stopwatch;
class isPrime
{
static sw sw = new sw();
static void Main()
{
test(1000000000);
Console.Read();
}
static void test(uint n)
{
int[] isP;
sw.Start();
isP = buildIsPrime(n);
sw.Stop();
if (n > 0) n -= 1 - (n & 1);
for (int i = 0; i < 10 && n > 1; n -= 2)
if ((isP[n >> 6] & 1 << (int)(n >> 1)) != 0)
{ Console.WriteLine(n); i++; }
}
static int[] buildIsPrime(uint n)
{
int y, d, e, q, r, s, i, j, u; int[] x, isP;
isP = new int[(n >> 6) + 1]; isP[0] = 2;
y = (int)(n / 3); x = new int[(y >> 5) + 1];
d = 8; e = 0; q = 3; r = 1; s = 7; i = 0; j = 10;
while (s < y)
{
if ((x[i >> 5] & 1 << i++) == 0)
{
int k = s, m = s + q;
for (; m < y; k += j, m += j) { x[k >> 5] |= 1 << k; x[m >> 5] |= 1 << m; }
for (; k < y; k += j) x[k >> 5] |= 1 << k;
}
e += 8; s += e; r += 8; j += 4;
if ((x[i >> 5] & 1 << i++) == 0 && s < y)
{
int k = s, m = s + r;
for (; m < y; k += j, m += j) { x[k >> 5] |= 1 << k; x[m >> 5] |= 1 << m; }
for (; k < y; k += j) x[k >> 5] |= 1 << k;
}
d += 16; s += d; q += 4; j += 8;
}
Console.WriteLine(sw.Elapsed + " x");
y -= 2; d = y >> 5; u = 2; n >>= 1;
for (i = 0; i < d; i++)
{
q = x[i];
if ((q & 1) == 0) isP[u >> 5] |= 1 << u; u += 1;
if ((q & 2) == 0) isP[u >> 5] |= 1 << u; u += 2;
if ((q & 4) == 0) isP[u >> 5] |= 1 << u; u += 1;
if ((q & 8) == 0) isP[u >> 5] |= 1 << u; u += 2; q >>= 4;
if ((q & 1) == 0) isP[u >> 5] |= 1 << u; u += 1;
if ((q & 2) == 0) isP[u >> 5] |= 1 << u; u += 2;
if ((q & 4) == 0) isP[u >> 5] |= 1 << u; u += 1;
if ((q & 8) == 0) isP[u >> 5] |= 1 << u; u += 2; q >>= 4;
if ((q & 1) == 0) isP[u >> 5] |= 1 << u; u += 1;
if ((q & 2) == 0) isP[u >> 5] |= 1 << u; u += 2;
if ((q & 4) == 0) isP[u >> 5] |= 1 << u; u += 1;
if ((q & 8) == 0) isP[u >> 5] |= 1 << u; u += 2; q >>= 4;
if ((q & 1) == 0) isP[u >> 5] |= 1 << u; u += 1;
if ((q & 2) == 0) isP[u >> 5] |= 1 << u; u += 2;
if ((q & 4) == 0) isP[u >> 5] |= 1 << u; u += 1;
if ((q & 8) == 0) isP[u >> 5] |= 1 << u; u += 2; q >>= 4;
if ((q & 1) == 0) isP[u >> 5] |= 1 << u; u += 1;
if ((q & 2) == 0) isP[u >> 5] |= 1 << u; u += 2;
if ((q & 4) == 0) isP[u >> 5] |= 1 << u; u += 1;
if ((q & 8) == 0) isP[u >> 5] |= 1 << u; u += 2; q >>= 4;
if ((q & 1) == 0) isP[u >> 5] |= 1 << u; u += 1;
if ((q & 2) == 0) isP[u >> 5] |= 1 << u; u += 2;
if ((q & 4) == 0) isP[u >> 5] |= 1 << u; u += 1;
if ((q & 8) == 0) isP[u >> 5] |= 1 << u; u += 2; q >>= 4;
if ((q & 1) == 0) isP[u >> 5] |= 1 << u; u += 1;
if ((q & 2) == 0) isP[u >> 5] |= 1 << u; u += 2;
if ((q & 4) == 0) isP[u >> 5] |= 1 << u; u += 1;
if ((q & 8) == 0) isP[u >> 5] |= 1 << u; u += 2; q >>= 4;
if ((q & 1) == 0) isP[u >> 5] |= 1 << u; u += 1;
if ((q & 2) == 0) isP[u >> 5] |= 1 << u; u += 2;
if ((q & 4) == 0) isP[u >> 5] |= 1 << u; u += 1;
if ((q & 8) == 0) isP[u >> 5] |= 1 << u; u += 2;
}
i <<= 5;
while (i < y)
{
if ((x[i >> 5] & 1 << i++) == 0) isP[u >> 5] |= 1 << u; u += 1;
if ((x[i >> 5] & 1 << i++) == 0) isP[u >> 5] |= 1 << u; u += 2;
}
if (u - 3 <= n - 3 && ((x[i >> 5] & 1 << i++) == 0)) isP[u >> 5] |= 1 << u; u += 1;
if (u - 3 <= n - 3 && ((x[i >> 5] & 1 << i++) == 0)) isP[u >> 5] |= 1 << u;
Console.WriteLine(sw.Elapsed + " p");
return isP;
}
}
/***********************************************************
Composites(4e9) 8.98 s, pi(4e9) 9.05 s. Bit Twiddling Hacks
*/
using System;
using sw = System.Diagnostics.Stopwatch;
class countPrimes
{
static sw sw = new sw();
static void Main()
{
test(4000000000);
}
static void test(uint n)
{
sw.Start();
Console.Write("pi(" + n + ") = " + pi(n));
sw.Stop();
Console.Read();
}
static uint pi(uint n)
{
int y, d, e, q, r, s, i, j; uint c, u; uint[] x;
if (n < 3) return n >> 1;
y = (int)(n / 3); x = new uint[(y >> 5) + 1];
d = 8; e = 0; q = 3; r = 1; s = 7; i = 0; j = 10;
while (s < y)
{
if ((x[i >> 5] & 1 << i++) == 0)
{
int k = s, m = s + q;
for (; m < y; k += j, m += j) { x[k >> 5] |= 1u << k; x[m >> 5] |= 1u << m; }
for (; k < y; k += j) x[k >> 5] |= 1u << k;
}
e += 8; s += e; r += 8; j += 4;
if ((x[i >> 5] & 1 << i++) == 0 && s < y)
{
int k = s, m = s + r;
for (; m < y; k += j, m += j) { x[k >> 5] |= 1u << k; x[m >> 5] |= 1u << m; }
for (; k < y; k += j) x[k >> 5] |= 1u << k;
}
d += 16; s += d; q += 4; j += 8;
}
Console.WriteLine(sw.Elapsed + " x");
c = 2; y -= 2; d = y >> 5;
for (i = 0; i < d; i++)
{ // Bit Twiddling Hacks
u = ~x[i];
u -= u >> 1 & 0x55555555;
u = (u & 0x33333333) + (u >> 2 & 0x33333333);
c += (u + (u >> 4) & 0xf0f0f0f) * 0x1010101 >> 24;
}
i <<= 5; u = 5 + 3 * (uint)i;
while (i < y)
{
if ((x[i >> 5] & 1 << i++) == 0) c++;
if ((x[i >> 5] & 1 << i++) == 0) c++; u += 6;
}
if (u - 3 <= n - 3 && ((x[i >> 5] & 1 << i++) == 0)) c++; u += 2;
if (u - 3 <= n - 3 && ((x[i >> 5] & 1 << i++) == 0)) c++;
Console.WriteLine(sw.Elapsed + " c");
return c;
}
}
/*******************************************************************************
primes(1e9) 2.12 s, primes(2e9) 4.61 s, primes(4e9) 9.90 s, primes(~0u) 10.65 s.
*/
using System;
using System.Threading.Tasks;
using sw = System.Diagnostics.Stopwatch;
class Eratosthenes
{
static sw sw = new sw();
static void Main()
{
test(1000000000);
Console.Read();
}
static void test(uint n)
{
uint pi_n; uint[] p;
sw.Start();
p = getPrimes(n);
sw.Stop();
pi_n = p[p.Length - 1];
Console.WriteLine("pi(" + n + ") = " + pi_n);
if (pi_n > 0)
Console.Write("largest prime = " + p[pi_n - 1]);
}
static uint[] getPrimes(uint n)
{
int c, y, d, e, q, r, s, i, j; uint u; double logN; int[] x; uint[] p;
if (n < 3) return n < 2 ? new uint[] { 0 } : new uint[] { 2, 1 };
logN = Math.Log(n);
c = (int)(n / logN * (1 + 1.2762 / logN));
p = new uint[c + 1]; p[0] = 2; p[1] = 3;
y = (int)(n / 3); x = new int[(y >> 5) + 1];
d = 8; e = 0; q = 3; r = 1; s = 7; i = 0; j = 10;
while (s < y)
{
if ((x[i >> 5] & 1 << i++) == 0)
{
int k = s, m = s + q;
for (; m < y; k += j, m += j) { x[k >> 5] |= 1 << k; x[m >> 5] |= 1 << m; }
for (; k < y; k += j) x[k >> 5] |= 1 << k;
}
e += 8; s += e; r += 8; j += 4;
if ((x[i >> 5] & 1 << i++) == 0 && s < y)
{
int k = s, m = s + r;
for (; m < y; k += j, m += j) { x[k >> 5] |= 1 << k; x[m >> 5] |= 1 << m; }
for (; k < y; k += j) x[k >> 5] |= 1 << k;
}
d += 16; s += d; q += 4; j += 8;
}
Console.WriteLine(sw.Elapsed + " x");
y = y <= 2 ? 0 : y - 2;
j = y < 32 ? 2 : paraPrimes(y >> 5, x, p);
i = y >> 5 << 5; u = 5 + 3 * (uint)i;
while (i < y)
{
if ((x[i >> 5] & 1 << i++) == 0) p[j++] = u; u += 2;
if ((x[i >> 5] & 1 << i++) == 0) p[j++] = u; u += 4;
}
if (u - 3 <= n - 3 && ((x[i >> 5] & 1 << i++) == 0)) p[j++] = u; u += 2;
if (u - 3 <= n - 3 && ((x[i >> 5] & 1 << i++) == 0)) p[j++] = u;
p[c] = (uint)j;
Console.WriteLine(sw.Elapsed + " p");
return p;
}
static int paraPrimes(int imax, int[] x, uint[] p)
{
int j0 = 0, j1 = 0;
Parallel.For(0, 2, k =>
{
int i, j, y; uint u;
if (k == 0) { i = 0; j = 2; u = 5; }
else { if (imax < 2) return; i = 1; j = 25; u = 101; }
for (; ; )
{
y = x[i];
if ((y & 1) == 0) p[j++] = u; u += 2; if ((y & 2) == 0) p[j++] = u; u += 4; y >>= 2;
if ((y & 1) == 0) p[j++] = u; u += 2; if ((y & 2) == 0) p[j++] = u; u += 4; y >>= 2;
if ((y & 1) == 0) p[j++] = u; u += 2; if ((y & 2) == 0) p[j++] = u; u += 4; y >>= 2;
if ((y & 1) == 0) p[j++] = u; u += 2; if ((y & 2) == 0) p[j++] = u; u += 4; y >>= 2;
if ((y & 1) == 0) p[j++] = u; u += 2; if ((y & 2) == 0) p[j++] = u; u += 4; y >>= 2;
if ((y & 1) == 0) p[j++] = u; u += 2; if ((y & 2) == 0) p[j++] = u; u += 4; y >>= 2;
if ((y & 1) == 0) p[j++] = u; u += 2; if ((y & 2) == 0) p[j++] = u; u += 4; y >>= 2;
if ((y & 1) == 0) p[j++] = u; u += 2; if ((y & 2) == 0) p[j++] = u; u += 4; y >>= 2;
if ((y & 1) == 0) p[j++] = u; u += 2; if ((y & 2) == 0) p[j++] = u; u += 4; y >>= 2;
if ((y & 1) == 0) p[j++] = u; u += 2; if ((y & 2) == 0) p[j++] = u; u += 4; y >>= 2;
if ((y & 1) == 0) p[j++] = u; u += 2; if ((y & 2) == 0) p[j++] = u; u += 4; y >>= 2;
if ((y & 1) == 0) p[j++] = u; u += 2; if ((y & 2) == 0) p[j++] = u; u += 4; y >>= 2;
if ((y & 1) == 0) p[j++] = u; u += 2; if ((y & 2) == 0) p[j++] = u; u += 4; y >>= 2;
if ((y & 1) == 0) p[j++] = u; u += 2; if ((y & 2) == 0) p[j++] = u; u += 4; y >>= 2;
if ((y & 1) == 0) p[j++] = u; u += 2; if ((y & 2) == 0) p[j++] = u; u += 4; y >>= 2;
if ((y & 1) == 0) p[j++] = u; u += 2; if ((y & 2) == 0) p[j++] = u; u += 4;
i += 2; if (i >= imax) { if (k == 0) j0 = j; else j1 = j; break; }
u += 96; j += bitsSet(~x[i - 1]);
}
});
return j0 > j1 ? j0 : j1;
}
static int bitsSet(int i)
{
i -= i >> 1 & 0x55555555;
i = (i & 0x33333333) + (i >> 2 & 0x33333333);
return (i + (i >> 4) & 0xf0f0f0f) * 0x1010101 >> 24;
}
}
/*******************************************************************
Faster isPrime time (s)
n x isP?
1e9 1.84 2.00
2e9 4.08 4.38
4e9 8.84 9.40
*/
using System;
using System.Threading.Tasks;
using sw = System.Diagnostics.Stopwatch;
class isPrime
{
static sw sw = new sw();
static void Main()
{
test((uint)1e9);
Console.Read();
}
static void test(uint n)
{
int[] isP;
sw.Start();
isP = buildIsPrime(n);
sw.Stop();
int check = 0; // n check
for (int i = isP.Length - 1; i >= 0; i--) // 1e9 1DF99124
check ^= isP[i]; // 2e9 E9D92C9E
Console.Write("check: {0:X8}", check); // 4e9 DB1F9720
}
static int[] buildIsPrime(uint n)
{
int y, i, u; int[] x, isP;
if (n < 64) return new int[] { 0x64b4cb6e };
isP = new int[(n >> 6) + 1]; isP[0] = 2;
y = (int)(n / 3); x = new int[(y >> 5) + 1];
mark(y, x);
y -= 2; n >>= 1;
paraIsPrime(y >> 5, x, isP);
u = (y >> 5 << 4) * 3 + 2; i = y >> 5 << 5;
while (i < y)
{
if ((x[i >> 5] & 1 << i++) == 0) isP[u >> 5] |= 1 << u; u += 1;
if ((x[i >> 5] & 1 << i++) == 0) isP[u >> 5] |= 1 << u; u += 2;
}
if (u - 3 <= n - 3 && ((x[i >> 5] & 1 << i++) == 0)) isP[u >> 5] |= 1 << u; u += 1;
if (u - 3 <= n - 3 && ((x[i >> 5] & 1 << i++) == 0)) isP[u >> 5] |= 1 << u;
Console.WriteLine(sw.Elapsed + " p");
return isP;
}
static void mark(int y, int[] z)
{
int u, v, w, x, s, i, j;
u = 8; v = 0; w = 3; x = 1; s = 7; i = 0; j = 10;
while (s < y)
{
if ((z[i >> 5] & 1 << i++) == 0)
{
int a = s, b = s + j, c = s + w, d = c + j, k = j << 1;
for (; d < y; a += k, b += k, c += k, d += k)
{
z[a >> 5] |= 1 << a; z[c >> 5] |= 1 << c;
z[b >> 5] |= 1 << b; z[d >> 5] |= 1 << d;
}
if (a < y)
{
z[a >> 5] |= 1 << a;
if (c < y) z[c >> 5] |= 1 << c;
if (b < y) z[b >> 5] |= 1 << b;
}
}
v += 8; s += v; x += 8; j += 4;
if ((z[i >> 5] & 1 << i++) == 0)
{
int a = s, b = s + j, c = s + x, d = c + j, k = j << 1;
for (; d < y; a += k, b += k, c += k, d += k)
{
z[a >> 5] |= 1 << a; z[c >> 5] |= 1 << c;
z[b >> 5] |= 1 << b; z[d >> 5] |= 1 << d;
}
if (a < y)
{
z[a >> 5] |= 1 << a;
if (c < y) z[c >> 5] |= 1 << c;
if (b < y) z[b >> 5] |= 1 << b;
}
}
u += 16; s += u; w += 4; j += 8;
}
Console.WriteLine(sw.Elapsed + " x");
}
static void paraIsPrime(int imax, int[] x, int[] z) // z = isP
{
int pc = Environment.ProcessorCount;
for (int n = 0; n < 2; n++)
{
Parallel.For(0, pc, k =>
{
int m, i, j, u, v, y;
if ((k & 1) == n)
{
j = pc * 2; v = (j - 1) * 48;
for (m = 0; m < 2; m++)
{
i = m + k * 2; u = 2 + i * 48;
for (; i < imax; i += j, u += v)
{
#region
y = x[i];
if ((y & 1) == 0) z[u >> 5] |= 1 << u; u += 1;
if ((y & 2) == 0) z[u >> 5] |= 1 << u; u += 2;
if ((y & 4) == 0) z[u >> 5] |= 1 << u; u += 1;
if ((y & 8) == 0) z[u >> 5] |= 1 << u; u += 2; y >>= 4;
if ((y & 1) == 0) z[u >> 5] |= 1 << u; u += 1;
if ((y & 2) == 0) z[u >> 5] |= 1 << u; u += 2;
if ((y & 4) == 0) z[u >> 5] |= 1 << u; u += 1;
if ((y & 8) == 0) z[u >> 5] |= 1 << u; u += 2; y >>= 4;
if ((y & 1) == 0) z[u >> 5] |= 1 << u; u += 1;
if ((y & 2) == 0) z[u >> 5] |= 1 << u; u += 2;
if ((y & 4) == 0) z[u >> 5] |= 1 << u; u += 1;
if ((y & 8) == 0) z[u >> 5] |= 1 << u; u += 2; y >>= 4;
if ((y & 1) == 0) z[u >> 5] |= 1 << u; u += 1;
if ((y & 2) == 0) z[u >> 5] |= 1 << u; u += 2;
if ((y & 4) == 0) z[u >> 5] |= 1 << u; u += 1;
if ((y & 8) == 0) z[u >> 5] |= 1 << u; u += 2; y >>= 4;
if ((y & 1) == 0) z[u >> 5] |= 1 << u; u += 1;
if ((y & 2) == 0) z[u >> 5] |= 1 << u; u += 2;
if ((y & 4) == 0) z[u >> 5] |= 1 << u; u += 1;
if ((y & 8) == 0) z[u >> 5] |= 1 << u; u += 2; y >>= 4;
if ((y & 1) == 0) z[u >> 5] |= 1 << u; u += 1;
if ((y & 2) == 0) z[u >> 5] |= 1 << u; u += 2;
if ((y & 4) == 0) z[u >> 5] |= 1 << u; u += 1;
if ((y & 8) == 0) z[u >> 5] |= 1 << u; u += 2; y >>= 4;
if ((y & 1) == 0) z[u >> 5] |= 1 << u; u += 1;
if ((y & 2) == 0) z[u >> 5] |= 1 << u; u += 2;
if ((y & 4) == 0) z[u >> 5] |= 1 << u; u += 1;
if ((y & 8) == 0) z[u >> 5] |= 1 << u; u += 2; y >>= 4;
if ((y & 1) == 0) z[u >> 5] |= 1 << u; u += 1;
if ((y & 2) == 0) z[u >> 5] |= 1 << u; u += 2;
if ((y & 4) == 0) z[u >> 5] |= 1 << u; u += 1;
if ((y & 8) == 0) z[u >> 5] |= 1 << u; u += 2;
#endregion
}
}
}
});
}
}
}
No comments:
Post a Comment