FuriousMathematician FuriousMathematician - 1 month ago 5
C Question

How to factorize a number?

I've been asked to factorize a number and show it in a specific way .

e.g: 100 = 2^2*5^2

This is the C++ code I've used so far with no dice , unfortunately:

#include <stdio.h>
#include <math.h>

//IsPrime indicates whether a given number is or is not prime.
bool IsPrime(long long n)
{
int j = 3;
if (n == 2)
{
return true;
}
else if (n % 2 == 0)
{
return false;
}
else
{
for (j = 3; j <= sqrt(n); j += 2)
{
if (n%j == 0)
{
return false;
}
}
}
return true;
}

int main(void)
{
long long n_orig,n, i=3 , primecount=0;
scanf("%lld", &n_orig);
n = n_orig;
if (n == 1)
{
printf("1");
return 0;
}
if (IsPrime(n))
{
printf("%lld", n);
return 0;
}
if (n % 2 == 0)
{
while (n >= 2 && n % 2 == 0)
{
primecount++;
n = n / 2;
}
if (primecount == 1)
{
printf("2*");
}
else
{
printf("2^%lld*", primecount);
}
}
primecount = 0;
n = n_orig;
while (i <= n/2)
{
if (IsPrime(i))
{
while (n >= i && n % i == 0)
{
primecount++;
n = n / i;
}
}
n = n_orig;
if (primecount == 0)
{
i++;
continue;
}
if (primecount == 1)
{
printf("%lld*", i);
}
else
{
printf("%lld^%lld*", i, primecount);
}
primecount = 0;
i+=2;
}
printf("\b");
return 0;
}


Using this code I was able to generate a few test cases, though when I uploaded my answer to the website where the codes are presumably evaluated , out of 7 test cases (which I cannot know what they exactly are) , I pass 3 , fail 3 and exceed time limit (the one that hasn't even been declared in the question) in one case. I'd really appreciate some help , and please be noob-friendly!

Also , I don't really wanna know if my answer could be improved in some way , my top priority right now is understanding why MY own code doesn't work as intended.

P.S : Usage of iostream and arrays is not allowed.

Thanks in advance.

Answer

Try this:

#include <stdio.h>
#include <math.h>

unsigned long long PrintMultiplicity(unsigned long long n,unsigned long long factor)
{
    int count = 0;

    while (n%factor == 0)
    {
        count++;
        n /= factor;
    }

    if (count > 0)
    {
        printf("%llu^%d",factor,count);
        if (n > 1)
            printf("*");
    }

    return n;
}

void PrintFactorization(unsigned long long n)
{
    unsigned long long factor;
    int add;

    printf("%llu = ",n);

    n = PrintMultiplicity(n,2);
    n = PrintMultiplicity(n,3);

    for (factor = 5, add = 2; factor <= sqrt(n); factor += add, add = 4-add)
        n = PrintMultiplicity(n,factor);

    if (n > 1)
        printf("%llu^1",n);

    printf("\n");
}

int main()
{
    unsigned long long n;
    scanf("%llu",&n);
    PrintFactorization(n);
    return 0;
}
Comments