count.cs

using System;
using System.Collections.Generic;
using System.Collections;

namespace app
{
    class Program
    {
        static void Main(string[] args)
        {
            // count n = pq where n in [a..b) and p, q in [u..v) intersection P.
            System.Console.WriteLine("input a, b, u, v");
            var buf = System.Console.ReadLine().Split();
            var a = ulong.Parse(buf[0]);
            var b = ulong.Parse(buf[1]);
            var u = ulong.Parse(buf[2]);
            var v = ulong.Parse(buf[3]);
            var pl = new List<ulong>();
            ulong ans = 0;
            foreach (var p in Eratosthenes(v))
            {
                if (p < u)
                {
                    continue;
                }
                pl.Add(p);
                foreach (var q in pl)
                {
                    var prod = p * q;
                    if (a <= prod && prod < b)
                    {
                        System.Console.WriteLine("{0}\t{1}\t{2}", p, q, prod); // comment out this line if you need only the number of numbers.
                        ans += 1;
                    }
                }
            }
            System.Console.WriteLine("Answer: {0}", ans);
            System.Console.ReadLine();
        }


        /// <summary>
        /// primes STRICTLY LESS THAN n
        /// </summary>
        /// <complexity>O(n lnln n) time, O(n) space</complexity>
        /// <param name="n"></param>
        /// <returns></returns>
        public static IEnumerable<ulong> Eratosthenes(ulong n)
        {
            if (n <= 2) yield break; // nothing to yield - terminate immediately.
            var not_prime = new bool[n];
            not_prime[0] = not_prime[1] = true;
            foreach (var i in less_than_sqrt(n))
            {
                if (not_prime[i])
                {
                    continue;
                }
                foreach (var j in multiple(i, n))
                {
                    not_prime[j] = true;
                }
            }
            foreach (var p in index(not_prime))
            {
                if (!not_prime[p])
                {
                    yield return p;
                }
            }
        }

        /// <summary>
        /// yields {i in N : i^2 < n}
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static IEnumerable<ulong> less_than_sqrt(ulong n)
        {
            for (ulong i = 0; i * i < n; i += 1)
            {
                yield return i;
            }
        }

        /// <summary>
        /// yields multiple of i in [i^2 .. n)
        /// </summary>
        /// <param name="i"></param>
        /// <param name="n"></param>
        /// <returns></returns>
        public static IEnumerable<ulong> multiple(ulong i, ulong n)
        {
            for (ulong j = i * i; j < n; j += i)
            {
                yield return j;
            }
        }

        /// <summary>
        /// yields [0..n)
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static IEnumerable<ulong> range(ulong n)
        {
            for (ulong i = 0; i < n; i += 1)
            {
                yield return i;
            }
        }

        /// <summary>
        /// yields index. of a IEnumerable.
        /// </summary>
        /// <param name="L"></param>
        /// <returns></returns>
        public static IEnumerable<ulong> index(IEnumerable L)
        {
            ulong i = 0;
            foreach (var x in L)
            {
                yield return i;
                i += 1;
            }
        }
    }

}