Skip to content

Instantly share code, notes, and snippets.

@kescherCode
Last active January 30, 2018 21:54
Show Gist options
  • Save kescherCode/c37ebd22c3f0bad7a20dab1614756ac7 to your computer and use it in GitHub Desktop.
Save kescherCode/c37ebd22c3f0bad7a20dab1614756ac7 to your computer and use it in GitHub Desktop.
DeletablePrimes Coding Contest exercise in C# - filthyCode
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.
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);
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment