prime number count

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Runtime.Intrinsics;
using System.Runtime.Intrinsics.X86;
using System.Threading.Tasks;
using System.Numerics;

class Program {
    static int Algo1(int size) {
        const int core = 8;
        const int MaxSafeInteger = 16_777_216;

        return (size > MaxSafeInteger ? 1_077_871 : 8) + Enumerable.Range(0, core).Select(i => Task.Run(() => {
            int count = 0;
            int known = size > MaxSafeInteger ? MaxSafeInteger + 1 : 21 ;
            int coreSize = (size - known) / core;
            int start = known + coreSize * i;
            if (start % 2 == 0) ++start;
            int end = i == core - 1 ? size : start + coreSize;

            int sqr = (int)Math.Sqrt(start);

            if (size <= MaxSafeInteger) {
                for (int current = start; current <= end; current += 2) {
                    if (sqr * sqr <= current) {
                        ++sqr;
                    }
                    var num = Vector256.Create((float)current);

                    for (var divisor = Vector256.Create(17f, 15f, 13f, 11f, 9f, 7f, 5f, 3f); ; divisor = Avx.Add(divisor, Vector256.Create(16f))) {
                        var div = Avx.Divide(num, divisor);
                        var temp = Avx.Compare(div, Avx.Floor(div), FloatComparisonMode.OrderedEqualNonSignaling);

                        if (!Avx.TestZ(temp, temp)) {
                            break; // not prime
                        }
                        if ((int)divisor.ToScalar() >= sqr) {
                            ++count;
                            break;
                        }
                    }
                }
            } else {
                for (int current = start; current < end; current += 2) {
                    if (sqr * sqr <= current) {
                        ++sqr;
                    }

                    var num = Vector256.Create((double)current);

                    for (var divisor = Vector256.Create(9d, 7d, 5d, 3d); ; divisor = Avx.Add(divisor, Vector256.Create(8d))) {
                        var div = Avx.Divide(num, divisor);
                        var temp = Avx.Compare(div, Avx.Floor(div), FloatComparisonMode.OrderedEqualNonSignaling);

                        if (!Avx.TestZ(temp, temp)) {
                            break; // not prime
                        }
                        if ((int)divisor.ToScalar() >= sqr) {
                            ++count;
                            break;
                        }
                    }
                }
            }

            return count;
        })).ToArray().Select(task => task.Result).Sum();
    }

    static int Old(int size) {
        int sqr = 4;
        int count = 8;

        for (int current = 21; current < size; current += 2) {
            if (sqr * sqr <= current) {
                ++sqr;
            }

            var num = Vector256.Create((double)current);

            for (var divisor = Vector256.Create(9d, 7d, 5d, 3d); ; divisor = Avx.Add(divisor, Vector256.Create(8d))) {
                var div = Avx.Divide(num, divisor);
                var temp = Avx.Compare(div, Avx.Floor(div), FloatComparisonMode.OrderedEqualNonSignaling);

                if (!Avx.TestZ(temp, temp)) {
                    break; // not prime
                }
                if ((int)divisor.ToScalar() >= sqr) {
                    ++count;
                    break;
                }
            }
        }

        return count;
    }

    static int TryDivide(int size) {
        var primes = new List<Vector256<float>>(134734) {
            Vector256.Create(16777216f, 16777216f, 16777216f, 16777216f, 16777216f, 16777216f, 3f, 2f)
        };
        int sqr = 2, maxSqr = (int)Math.Sqrt(size);
        int pos = Vector256<float>.Count - 3;
        bool flag = true;
        int fastSize = Math.Min(size, 16777216);
        int current = 5;
        int count = 2;

        for (; current <= fastSize; current += (flag = !flag) ? 4 : 2) {
            var num = Vector256.Create((float)current);
            if (sqr * sqr <= current) {
                ++sqr;
            }

            for (var i = 0; i < primes.Count; ++i) {
                var divisor = primes[i];
                var div = Avx.Divide(num, divisor);
                var temp = Avx.Compare(div, Avx.Floor(div), FloatComparisonMode.OrderedEqualNonSignaling);
                if (!Avx.TestZ(temp, temp)) {
                    break; // not prime
                }
                if ((int)divisor.ToScalar() >= sqr) {
                    // prime number found
                    ++count;
                    if (current <= maxSqr) {
                        // we only stores values <= sqrt(size)
                        primes[primes.Count - 1] = primes[primes.Count - 1].WithElement(pos, current);
                        if (--pos < 0) {
                            primes.Add(Vector256.Create(16777216f));
                            pos = Vector256<float>.Count - 1;
                        }
                    }

                    break;
                }
            }
        }

        if (current <= size) {
            do {
                var num = Vector256.Create((double)current);
                if (sqr * sqr <= current) {
                    ++sqr;
                }

                for (var i = 0; i < primes.Count; ++i) {
                    for (byte j = 1; j != byte.MaxValue; --j) {
                        var divisor = Avx.ConvertToVector256Double(Avx.ExtractVector128(primes[i], j));
                        var div = Avx.Divide(num, divisor);
                        var temp = Avx.Compare(div, Avx.Floor(div), FloatComparisonMode.OrderedEqualNonSignaling);
                        if (!Avx.TestZ(temp, temp)) {
                            goto next; // not prime
                        }
                        if ((int)divisor.ToScalar() >= sqr) {
                            // prime number found
                            ++count;
                            goto next;
                        }
                    }
                }

            next:
                current += (flag = !flag) ? 4 : 2;
            } while (current <= size);
        }

        return count;
    }

    static int Select(int size) {
        var span = new Span<ulong>(new ulong[size / 32 + 1]);
        span.Fill(ulong.MaxValue);
        BitOps.ClearBit(ref span[0], 0);

        for (var i = 0; i < size / 32; ++i) {
            for (var j = 0; j < 32; ++j) {

                var lz = BitOperations.TrailingZeroCount(span[i] & (~0Lu >> j));
                Console.WriteLine(lz);

                int k = lz, n;
                n = BitOperations.TrailingZeroCount(span[i] & (~0Lu >> k << k));
                BitOps.ClearBit(ref span[i], (lz + 1) * (n + 1) - 1);
                ++k;

                n = BitOperations.TrailingZeroCount(span[i] & (~0Lu >> k << k));
                BitOps.ClearBit(ref span[i], (lz + 1) * (n + 1) - 1);
            }
        }
        return size;
    }

    static void Main() {
        const int size = 32;
        var watch = Stopwatch.StartNew();
        Console.WriteLine("{0}: {1}", size, Select(size));
        watch.Stop();
        Console.WriteLine(watch.Elapsed);
    }
}