DeletablePrimes Coding Contest exercise in C# - filthyCode

README

A simple program that determimes if a prime is a so-called deletable prime.
I coded this for an exercise on http://catcoder.codingcontest.org in about 5 minutes.
I only finished with an 8 minute time though, because I also had to make IsPrime() more efficient due to large numbers taking too long.

Program.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DeleteablePrimes
{
    class Program
    {
        // I don't like Math.Pow()
        static ulong IntPower(uint _base, int n)
        {
            if (n == 0)
            {
                return 1;
            }

            if (n == 1)
            {
                return _base;
            }

            int m = n / 2;
            ulong res = IntPower(_base, m);
            return (res * res * IntPower(_base, n % 2));
        }

        static ulong RemoveDigit(ulong number, int position)
        {
            const uint _base = 10;

            ulong factor1 = IntPower(_base, position); // std::pow( base, pos );
            ulong factor2 = _base * factor1;      // std::pow( base, pos + 1 );

            // n / 10^pos * 10^pos => removes all the digits from pos until the least significant digits
            ulong truncatedVal1 = (number / factor1) * factor1;

            // n / 10^(pos+1) * 10^(pos+1) => removes all the digits from pos, included until the least significant digits
            ulong truncatedVal2 = (truncatedVal1 / factor2) * factor2;

            //delete 1 position by dividing with the 10 then add the remaining digits
            return truncatedVal2 / _base + (number - truncatedVal1);
        }
        static bool IsPrime(ulong number)
        {
                if (number == 1)
                {
                    return false;
                }

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

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

                double squareRoot = Math.Sqrt(number);

                for (double d = 3; d <= squareRoot; d += 2)
                {
                    if (!(number % d != 0))
                    {
                        return false;
                    }
                }

                return true;
        }

        // Returns the number of possible paths for a deletable prime.
        static int GetNumberOfPaths(int _numDigits, ulong number)
        {
            int paths = 0;
            ulong tempNum;
            for (int i = 0; i < _numDigits; i++)
            {
                tempNum = number;
                _numDigits = number.ToString().Length;

                if (_numDigits > 1)
                    tempNum = RemoveDigit(number, i);

                bool valid = number.ToString().Length - tempNum.ToString().Length < 2;
                // e.g. 10859 would be valid without above line. Removing the 1 would remove the 0, no other way to go down one path = no deletable prime.

                if (IsPrime(tempNum) && valid)
                {
                    if (tempNum / 10 == 0)
                    {
                        paths++;
                    }
                    else
                    {
                        // Recursion is helpful
                        paths += GetNumberOfPaths(_numDigits, tempNum);
                    }
                }
            }

            return paths;
        }

        // Checks if a number is a deletable prime
        static bool IsDeleteablePrime(ulong number)
        {
            return GetNumberOfPaths(number.ToString().Length, number) > 0;
        }

        static void Main(string[] args)
        {
            List<ulong> numsToCheck = new List<ulong>();

            while (true)
            {
                string numStr = Console.ReadLine();
                if (ulong.TryParse(numStr.Trim(), out ulong number))
                {
                    numsToCheck.Add(number);
                }
                else
                {
                    if (numStr.Trim() == "")
                    {
                        break; // End entry

                    }
                    else
                    {
                        Console.WriteLine("Invalid input");
                    }
                }
            }

            foreach (ulong number in numsToCheck)
            {
                Console.WriteLine(GetNumberOfPaths(number.ToString().Length, number));
            }

            if (System.Diagnostics.Debugger.IsAttached)
            {
                Console.WriteLine("Press any key...");
                Console.ReadKey(true);
            }
        }
    }
}