HackerRank: Leonardo's Prime Factors

It's been a while since I have solved a HR problem (last time was pre-pandemic). For this one all you need to do is generate the product of primes <= 10^18. Do it once and store the results in a sorted data structure, such as a sorted list. For each n (1<=n<=10^5) do a lookup into the sorted data structure. Overall execution time then becomes O(N*logM) where N~10^5 and M~10^18. Code is down below, cheers, Another Casual Coder (ACC).

Leonardo's Prime Factors | HackerRank

Leonardo loves primes and created  queries where each query takes the form of an integer, . For each , count the maximum number of distinct prime factors of any number in the inclusive range .

Note: Recall that a prime number is only divisible by  and itself, and  is not a prime number.

Example

The maximum number of distinct prime factors for values less than or equal to  is . One value with  distinct prime factors is . Another is .

Function Description

Complete the primeCount function in the editor below.

primeCount has the following parameters:

• int n: the inclusive limit of the range to check

Returns

• int: the maximum number of distinct prime factors of any number in the inclusive range .

Input Format

The first line contains an integer, , the number of queries.
Each of the next  lines contains a single integer, .

Constraints

Sample Input

6
1
2
3
500
5000
10000000000

Sample Output

0
1
1
4
5
10

Explanation

1.  is not prime and its only factor is itself.
2.  has  prime factor, .
3. The number  has  prime factor, ,  has  and  has  prime factors.
4. The product of the first four primes is . While higher value primes may be a factor of some numbers, there will never be more than  distinct prime factors for a number in this range.

using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;
using System.Numerics;

class Result
{
    private static SortedList maxProductPerN = null;
    /*
     * Complete the 'primeCount' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts LONG_INTEGER n as parameter.
     */

    public static int primeCount(long n)
    {
        if(maxProductPerN == null)
            maxProductPerN = (new Result()).MaxNumberProductPrimesLessThanN(BigInteger.Parse("1000000000000000000"));
        
        int previous = 1;
        foreach(long k in maxProductPerN.Keys)
        {
            if(k <= n)
            {
                previous = maxProductPerN[k];
            }
            else break;
        }
        
        return previous;
    }
    
    public SortedList MaxNumberProductPrimesLessThanN(BigInteger N)
    {
        int count = 0;

        SortedList maxProductPerN = new SortedList();
        maxProductPerN.Add(1L, 0);

        BigInteger product = 1;
        BigInteger prime = 2;
        while (product * prime <= N)
        {
            if (IsPrimeMillerRabin(prime))
            {
                product *= prime;
                count++;
                maxProductPerN.Add((long)product, count);
            }
            prime++;
        }

        Console.WriteLine(product);
        return maxProductPerN;
    }
    
        public bool IsPrimeMillerRabin(BigInteger n)
    {
        //It does not work well for smaller numbers, hence this check
        int SMALL_NUMBER = 1000;

        if (n <= SMALL_NUMBER)
        {
            return IsPrime(n);
        }

        int MAX_WITNESS = 100;
        for (long i = 2; i <= MAX_WITNESS; i++)
        {
            if (IsPrime(i) && Witness(i, n) == 1)
            {
                return false;
            }
        }

        return true;
    }

    public BigInteger SqRtN(BigInteger N)
    {
        /*++
         *  Using Newton Raphson method we calculate the
         *  square root (N/g + g)/2
         */
        BigInteger rootN = N;
        int count = 0;
        int bitLength = 1;
        while (rootN / 2 != 0)
        {
            rootN /= 2;
            bitLength++;
        }
        bitLength = (bitLength + 1) / 2;
        rootN = N >> bitLength;

        BigInteger lastRoot = BigInteger.Zero;
        do
        {
            if (lastRoot > rootN)
            {
                if (count++ > 1000)                   // Work around for the bug where it gets into an infinite loop
                {
                    return rootN;
                }
            }
            lastRoot = rootN;
            rootN = (BigInteger.Divide(N, rootN) + rootN) >> 1;
        }
        while (!((rootN ^ lastRoot).ToString() == "0"));
        return rootN;
    }

    public bool IsPrime(BigInteger n)
    {
        if (n <= 1)
        {
            return false;
        }

        if (n == 2)
        {
            return true;
        }

        if (n % 2 == 0)
        {
            return false;
        }

        for (int i = 3; i <= SqRtN(n) + 1; i += 2)
        {
            if (n % i == 0)
            {
                return false;
            }
        }
        return true;
    }

    private int Witness(long a, BigInteger n)
    {
        BigInteger t, u;
        BigInteger prev, curr = 0;
        BigInteger i;
        BigInteger lln = n;

        u = n / 2;
        t = 1;
        while (u % 2 == 0)
        {
            u /= 2;
            t++;
        }

        prev = BigInteger.ModPow(a, u, n);
        for (i = 1; i <= t; i++)
        {
            curr = BigInteger.ModPow(prev, 2, lln);
            if ((curr == 1) && (prev != 1) && (prev != lln - 1)) return 1;
            prev = curr;
        }
        if (curr != 1) return 1;
        return 0;
    }

}

class Solution
{
    public static void Main(string[] args)
    {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        int q = Convert.ToInt32(Console.ReadLine().Trim());

        for (int qItr = 0; qItr < q; qItr++)
        {
            long n = Convert.ToInt64(Console.ReadLine().Trim());

            int result = Result.primeCount(n);

            textWriter.WriteLine(result);
        }

        textWriter.Flush();
        textWriter.Close();
    }
}