Pagina's

2020/02/14

A055932


/* A055932 Numbers all of whose prime divisors are consecutive primes starting at 2
Examples 2 4=2.2 6=2.3 8=2.2.2 12=2.2.3 16=2.2.2.2 18=2.3.3 24=2.2.2.3 30=2.3.5
The largest limit(m) is 3129970635269988509 (~ 3e18), 
1695808 terms, largest one: 3129968285335791900 in 27 ms.
*/
using System;  // 4790@3.6
namespace A055932
{
    class Program
    {
        static void Main()
        {
            var w = System.Diagnostics.Stopwatch.StartNew();
            Console.Write(C((ulong)1e18) + " " + w.Elapsed); Console.Read();
        }

        static int C(ulong m) { return new A055932(m).a.Length; } 
    }

    class A055932
    {
        public ulong[] a; int _i;
        public A055932(ulong m)  // A055932 <= m
        {
            byte[] p = { 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53 };
            m >>= 1; a = new ulong[8]; ulong pow = 3, Π = 3, aj; uint pi;
            while (pow <= m) { add(pow); pow *= 3; }
            int i = 0, j0 = 0, j, k;
        L0: pi = p[i++]; Π *= pi;
            if (Π > m) goto L2; pow = pi; j = k = j0; j0 = _i;
        L1: aj = pow * a[j++];
            if (aj > m) { Array.Sort(a, j0, _i - j0); goto L0; }
            do { add(aj); aj = pow * a[j++]; } while (aj <= m);
            pow *= pi; j = k; goto L1;
        L2: m <<= 1; if (m > 1) add(1); j = _i - 1;
            while (j >= 0) { aj = a[j--] <<= 1; while ((aj <<= 1) <= m) add(aj); }
            Array.Resize(ref a, _i);
        }
        void add(ulong v) { if (_i >= a.Length) Array.Resize(ref a, a.Length << 1); a[_i++] = v; }
    }
}