largest_power.cpp File Reference

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

#include <cassert>
#include <cstdint>
#include <iostream>

Include dependency graph for largest_power.cpp:

Go to the source code of this file.

Namespaces
namespace	math
	for assert

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

Definition in file largest_power.cpp.

Function Documentation

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 74 of file largest_power.cpp.

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

test()

static void test ( )

static

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

Returns

void

Definition at line 48 of file largest_power.cpp.

                   {
    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;
}