FuriousMathematician - 7 months ago 47
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.

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;

printf("%llu = ",n);

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

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;
}
Source (Stackoverflow)