Another Casual Coder

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

6
1
2
3
500
5000
10000000000

0
1
1
4
5
10

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();
 }
}