Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
|
Count the number of ciphers in n!
implementation
More...
#include <cassert>
#include <iostream>
Namespaces | |
namespace | bit_manipulation |
for IO operations | |
namespace | count_of_trailing_ciphers_in_factorial_n |
Functions for the Count the number of ciphers in n! implementation. | |
Functions | |
uint64_t | bit_manipulation::count_of_trailing_ciphers_in_factorial_n::numberOfCiphersInFactorialN (uint64_t n) |
Function to count the number of the trailing ciphers. | |
static void | test () |
Self-test implementations. | |
int | main () |
Main function. | |
Count the number of ciphers in n!
implementation
Given an integer number as input. The goal is to find the number of trailing zeroes in the factorial calculated for that number. A factorial of a number N is a product of all numbers in the range [1, N].
We know that we get a trailing zero only if the number is multiple of 10 or has a factor pair (2,5). In all factorials of any number greater than 5, we have many 2s more than 5s in the prime factorization of that number. Dividing a number by powers of 5 will give us the count of 5s in its factors. So, the number of 5s will tell us the number of trailing zeroes.
int main | ( | void | ) |
uint64_t bit_manipulation::count_of_trailing_ciphers_in_factorial_n::numberOfCiphersInFactorialN | ( | uint64_t | n | ) |
Function to count the number of the trailing ciphers.
n | number for which n! ciphers are returned |
n!
.
|
static |
Self-test implementations.