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 std::rand

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

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: