largest_power.cpp File Reference

Algorithm to find largest x such that p^x divides n! (factorial) using Legendre's Formula. More...

#include <iostream>
#include <cassert>

Include dependency graph for largest_power.cpp:

Namespaces
namespace	math
	for IO operations

Functions
uint64_t	math::largestPower (uint32_t n, const uint16_t &p)
	Function to calculate largest power.
static void	test ()
	Function for testing largestPower function. test cases and assert statement.
int	main ()
	Main function.

Detailed Description

Algorithm to find largest x such that p^x divides n! (factorial) using Legendre's Formula.

Given an integer n and a prime number p, the task is to find the largest x such that p^x (p raised to power x) divides n! (factorial). This will be done using Legendre's formula: x = [n/(p^1)] + [n/(p^2)] + [n/(p^3)] + \ldots + 1

See also

more on https://math.stackexchange.com/questions/141196/highest-power-of-a-prime-p-dividing-n

Author

uday6670

Function Documentation

main()

int main

(

void

)

Main function.

Returns

0 on exit

{ 
    test(); // execute the tests
    return 0;
} 

Here is the call graph for this function:

test()

static void test ( )

static

Function for testing largestPower function. test cases and assert statement.

Returns

void

{
    uint8_t test_case_1 = math::largestPower(5,2);
    assert(test_case_1==3);
    std::cout<<"Test 1 Passed!"<<std::endl;
    
    uint16_t test_case_2 = math::largestPower(10,3);
    assert(test_case_2==4);
    std::cout<<"Test 2 Passed!"<<std::endl;
    
    uint32_t test_case_3 = math::largestPower(25,5);
    assert(test_case_3==6);
    std::cout<<"Test 3 Passed!"<<std::endl;
    
    uint32_t test_case_4 = math::largestPower(27,2);
    assert(test_case_4==23);
    std::cout<<"Test 4 Passed!"<<std::endl;
    
    uint16_t test_case_5 = math::largestPower(7,3);
    assert(test_case_5==2);
    std::cout<<"Test 5 Passed!"<<std::endl;
} 

Here is the call graph for this function: