So I am running into an issue that I can't seem to fix. I want to display the factor and the power that it is raised to(basically prime factor decomposition), I had done this in python but for some reason I can't implement this in C and this is what I came up with
#include<stdio.h>
#include<math.h>
int main()
{
int i = 2, p, c, n;
scanf("%d", n);
while (n > 9)
{
p = 0;
c = 1;
while (n % i == 0)
{
for (int d = 2; d <= i / 2 + 1; d++)
if (i % d == 0 && i % 2 != 0)
c = 0;
if (c == 1)
{
p = p + 1;
n = n / i;
}
if (p != 0)
{
printf("%d %d", i, p);
printf("\n");
}
i = i + 1;
}
}
return 0;
}
Problem #1 (although it's not your main problem) is that you're missing a pointer in your scanf call:
scanf("%d", n);
That needs to be
scanf("%d", &n);
(My compiler warned me about this right away. Not sure why yours didn't.)
Problem #2 is that while (n > 9) is just totally wrong. I think you want while (n > 1).
Problem #3 is that the i = i + 1 step is misplaced. You need to do that whether or not i was a factor, so it needs to be at the end of the outermost loop.
And then problem #4 is the code that starts with
for (int d = 2; d <= i / 2 + 1; d++)
It looks like you're trying to check whether i is prime, although you're doing it too late: you're already inside the if where you test whether i is a factor of n. Also you don't have a proper loop to count how many times i is a factor of n.
It turns out, though, that you don't actually need to test whether i is prime, so let's leave the primality-testing step out for a moment and see what happens.
Here's the first fixed version:
#include <stdio.h>
int main()
{
int i = 2, p, n;
scanf("%d", &n);
while (n > 1)
{
if (n % i == 0) /* if i is a factor */
{
p = 0;
while (n % i == 0) /* count how many times i is a factor */
{
n /= i;
p++;
}
printf("%d %d\n", i, p);
}
i++;
}
return 0;
}
And this works! It tries every possible value of i, which is pretty inefficient, but due to the properties of prime factorization, it's okay. It tries them in order, so it will always have weeded out all lower prime factors first, so none of the non-prime i's will make it through to get printed as a factor.
To do what I guess you were trying to do, we have to rearrange the code. The basic algorithm is: for each i, if it's prime, see how many times it divides the running n.
#include <stdio.h>
int main()
{
int i = 2, p, c, n;
scanf("%d", &n);
while (n > 1)
{
/* see if i is prime */
c = 1;
for (int d = 2; d <= i / 2 + 1; d++)
if (i % d == 0 && i % 2 != 0)
{
c = 0;
break;
}
if (c == 1) /* if i is prime */
{
p = 0;
while (n % i == 0) /* count how many times i is a factor */
{
p = p + 1;
n = n / i;
}
if (p != 0)
printf("%d %d\n", i, p);
}
i = i + 1;
}
return 0;
}
The primality test is still pretty crude (that line if (i % d == 0 && i % 2 != 0) is fishy), but it seems to work. I suspect it's still wasteful, though: if you're generating all possible trial divisors to factorize n, there's probably a better way than running a full primality test on each i, from scratch.
One popular shortcut is to have i run through 2,3,5,7,9,11,13,... (that is, 2 plus all the odd numbers). Building on that idea, I once wrote some code that uses a more complicated sequence of increments so that it ends up using 2, 3, 5, and then every odd number that isn't a multiple of 3 or 5. I suspect (but I haven't measured) that wastefully using some number of non-prime trial divisors i might end up being less wasteful than positively confirming that each trial divisor is strictly prime.
But if you really care about efficiency, you'll have to abandon this obvious but still rather brute-force technique of blindly trying all the trial divisors, and move to something more sophisticated like elliptic curve factorization. What we're doing here is trial division, which as Wikipedia notes is "the most laborious but easiest to understand of the integer factorization algorithms".