Anomaly in program related to legendre's formula

Question

First of all, I would clarify that I am new to programming and started with c++ recently. There was a problem related to Legendre's formula in my math textbook and I thought about making a program related to it. It takes a number from user n, and finds the highest power of n which divides n!

It runs fine for a lot of numbers but messes up for a few others and it is completely random. This is a snippet from the code.

#include <iostream>
#include <math.h>

using namespace std;

int prime(int);
int calc(int, int);
int main()
{
    int n;
    int hpf=2;
    cout<<"This program finds highest power x that divides x!"<<endl;
    cout << "Enter number : " << endl;
    cin>>n;
    for(int i=2; i<=n; i++)
    {
        bool p=prime(i);
        if(p==true && n%i==0)
            hpf=i;
    }
    cout<<"The highest prime factor of the number is : "<<hpf<<endl;
    int p=calc(hpf, n);
    cout<<"The highest power of "<<n<<" that divides "<<n<<"!"<<" is : "<<p;
    return 0;
}

calc(int f, int n)
{
    int c=0 , d=1, power=1, i=0;
    while(i>=0)
    {
        int x= pow(f,power+i);
        if(i>0 && n%x==0)
            d++;
        if(x<=n)
        {
            c+=n/x;
            i++;
        }
        else
            break;
    }
    return c/d;
}

prime(int n)
{
   bool isPrime = true;
   for(int i = 2; i <= n/2; i++)
    {
      if (n%i == 0)
      {
         isPrime = false;
         break;
      }
    }
   return isPrime;
}

I pass the highest prime factor of n and the number n itself to int calc(int, int).

Now here is the problem:

when I input n=9, I get

Enter number :
9
The highest prime factor of the number is : 3
The highest power of 9 that divides 9! is : 2

on the other hand, if I input 25, I get

Enter number :
25
The highest prime factor of the number is : 5
The highest power of 25 that divides 25! is : 6

This is clearly wrong, the highest power should be 3.

It also works for bigger numbers accurately, but not all.

PS: I use codeblocks.

Answer 1

I'm not sure why exactly it works for 9 and not for 25(your program seems fine, but you probably have a problem when you calculate d or something), although both are squares of primes and your code seems to take care of that, but I do know why it doesn't work with number like 12. This happens because your code only looks at the highest prime factor and ignores the others. This will give you the true result when the other prime factors appear less frequently then the biggest one, but in all other cases this assumption leads to wrong results, because the highest is then also limited by smaller primes. So a correct solution has to take care of all prime factors.

For that you first need to factor the number(getting the prime factors and their power!). You can just google that if you are unsure how to do that. I don't want to include it here because then the answer would get to long.

Then you need to find how often the number is present in the factorial. As you already know(at least you used it in your code) you can count by summing up the occurence as a factor of each power of the prime in every factor of the factorial which can be done through division like this:

n/p¹ + n/p² + n/p³ + n/p⁴ + …

That can be put into a simple function(using a simple self-made power calculation):

int occurenceInFaculty(int factor, int faculty) {
    int sum = 0;
    for(int power = factor; power <= faculty; power *= factor) { // Go through all powers
        sum += faculty/power;
    }
    return sum;
}

Now you can calculate the occurrence for each of the prime factors of your number and if you divide by the power of that prime factor in the factorization you get an upper limit for the highest power. Then all that's left to do is take the minimum over all prime factors and you are done. Assuming one possible way of storing the prime factorization here is what the resulting code could look like:

Somewhere in the beginning of your code:

typedef struct {
    int prime;
    int power;
} PrimeFactor;

Assuming a prime factorization method like this:

PrimeFactor* factorization(int number, int* factors) {
    // Factorize here. Return a pointer to an array of PrimeFactors and set the pointer factors to the arrays length.
}

And then the calculation part:

int number = 25; // Put your number here.
int length = 0;
PrimeFactor* factors = factorization(25, &length);
int min = number; // Some reasonable upper border because n! < n^n
for(int i = 0; i < length; i++) {
    if(occurenceInFaculty(factors[i].prime, number)/factors[i].power < min)
        min = occurenceInFaculty(factors[i].prime, number)/factors[i].power;
}

This program also gets 25 right!