Prime Factorization

Hi you all! This is my very first post in the forum :P I'm sorry for my english, that's because I'm from Portugal.
Anyway, I have this work assignment I need to do for school but was in need of your help with the last part of it.
As in the tittle, I need a function that factorizes a given number n into his prime factors. Something like:

"Write a number: 600
600 = 2^3 * 3^1 * 5^2 "

I need to do that funtion using only ifs, whiles, etc. well... the most basics you can imagine. So I can't use any arrays or for cicles, wich I think would make it easier...

I did a little search in the forum and I found this "code" written by a user in other post:

Code:

n = number entered by user
sqrt_n = sqrt(n)
i = 2
while n > 1 and i <= sqrt_n
    if n is divisible by i
        add i to list of prime factors
        count = 1
        n = n / i
        while n is divisible by i
            increment count
            n = n / i
        add count to list of prime factor counts
    increment i
if n > 1
    add n to list of prime factors
    add 1 to list of prime factor counts

I think something like this is what I need, but a need to understand it, I need to add the part where it prints "2^3 * 3^4......" and basically I need to code it.

If you could help with this it would be great.
Thank you in advance.

Just count how many times x evenly divides out of n if you consider n to be the number you are factoring and x to be your factor.

I don't know if I understood what you said.
For a given number, a big number, I will have more than one factor. I don't know, from the start how many factors I will have, how do I assign variables (x, y, z...) to all of them to then count the times they divide?

I would design a function like this:

Example:

Code:

/*
 *  Returns how many times `factor` evenly goes into `number`
 */
int n_powers(int number, int factor)
{
  int n;

  for(n = 0; !(number % factor); number /= factor)
    ++n;

  return n;
}

Does that make sense to you?

Originally Posted by johnkisera123

I don't know if I understood what you said.
For a given number, a big number, I will have more than one factor. I don't know, from the start how many factors I will have, how do I assign variables (x, y, z...) to all of them to then count the times they divide?

You have no way of knowing in advance how many there are, and therefore you have no way of naming them. Fortunately you don't have to store them, you just have to print them.

Psh... I liked my n_powers() function, tabstop. I have an arbitrary precision math library that I wrote that resolves prime factorization more like how you are doing it, and simply adds exponents whenever a duplicate is found in a linked list of numbers.

Thank you for your answers. I tried to "code" the little piece of pseudo-code I posted before and it turns out that's all it is to it! It's solved, it works!!

So my code now is:

Code:

void decomposicao ( int n) {

double sqrt_n = sqrt (n);
int i = 2;
int count;

while (n > 1 && i <= sqrt_n) {
  if (n % i == 0){
        printf ("%d ^ ", i);
        count = 1;
        n = n / i;
        while (n % i == 0) {
              count = count + 1;
              n = n / i;
              }
        printf ("%d * ", count);
        }
  i = i + 1;
  }

}

As I said I couldn't use "for" loops in this assignment. I've learned them (and by the I don't understand what's the advantage in comparison with "while" loops) but I couldn't yet use them.
I just have two more questions, now that it works. I need to understand what the program is doing. So can anyone explain me:

1) how does the program know which factors are primes and which aren't??
2) what is that square root doing there??
(i think these two questions are basically the same but I'm not sure... :P)

1) how does the program know which factors are primes and which aren't??

It is implicit in the algorithm. You start with a prime and keep dividing until the result is not divisible by the prime. Then you look for the next integer that is a factor. This integer must be a prime. If it were not a prime, it would have prime factors less than itself, but you have already accounted for all possible prime factors less than this factor.

2) what is that square root doing there??

It does not need to be there. It is used to allow the algorithm to terminate early, but the algorithm can terminate as soon as i > n, since a factor cannot be greater than the product.