Skip to content

Instantly share code, notes, and snippets.

@trlewis
Last active August 29, 2015 14:08
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save trlewis/c7e2c796fe713a1b1c6f to your computer and use it in GitHub Desktop.
Save trlewis/c7e2c796fe713a1b1c6f to your computer and use it in GitHub Desktop.
factorial zeroes
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace PrimeFactorization
{
class Program
{
static void Main(string[] args)
{
int n = 0;
Console.Write("Enter a number n, or -1 to quit: ");
string str = Console.ReadLine();
n = int.Parse(str); //convert string to int
while(n >= 0)
{
CountZeroesAtEndOfFactorial(n);
Console.Write("Enter a number n, or -1 to quit: ");
str = Console.ReadLine();
n = int.Parse(str);
}
}
private static void CountZeroesAtEndOfFactorial(int number)
{
List<int> factors = GetPrimeFactorizationOfFactorial(number);
int twos = 0, fives = 0;
foreach (int num in factors)
{
if (num == 2)
twos = twos + 1;
if (num == 5)
fives = fives + 1;
}
int zeroCount = (twos < fives) ? twos : fives; //get the smaller quantity
Console.WriteLine("{0}! has {1} zeroes at the end", number, zeroCount);
}
private static List<int> GetPrimeFactorizationOfFactorial(int num)
{
List<int> list = new List<int>();
if (num < 2)
{
list.Add(num);
return list;
}
for (int i = 2; i <= num; i++)
list.AddRange(GetPrimeFactorization(i));
return list;
}
private static List<int> GetPrimeFactorization(int num)
{
List<int> list = new List<int>();
if (IsPrime(num))
{
list.Add(num);
return list;
}
int i = 2;
while (i * i <= num)
{
if (num % i == 0)
{
int result = num / i;
if (IsPrime(result))
list.Add(result);
else
list.AddRange(GetPrimeFactorization(result));
if (IsPrime(i))
list.Add(i);
else
list.AddRange(GetPrimeFactorization(i));
return list;
}
i++;
}
return list;
}
private static bool IsPrime(int num)
{
if (num == 1)
return false;
if (num == 2)
return true;
int i = 2;
while (i * i <= num)
{
if (num % i == 0)
return false;
i++;
}
return true;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment