Thread: Prime Factorization

  1. #1
    Registered User
    Join Date
    Nov 2008
    Posts
    3

    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.

  2. #2
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    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.

  3. #3
    Registered User
    Join Date
    Nov 2008
    Posts
    3
    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?

  4. #4
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    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 &#37; factor); number /= factor)
        ++n;
    
      return n;
    }
    Does that make sense to you?

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by johnkisera123 View Post
    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.

  6. #6
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    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.

  7. #7
    Registered User
    Join Date
    Nov 2008
    Posts
    3
    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)

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Prime Factorization
    By jack_carver in forum C Programming
    Replies: 0
    Last Post: 07-02-2009, 07:16 AM
  2. prime number program with function
    By mackieinva in forum C Programming
    Replies: 17
    Last Post: 09-20-2007, 08:36 AM
  3. prime numbers, counters, help!
    By vege^ in forum C++ Programming
    Replies: 1
    Last Post: 03-10-2003, 04:32 PM
  4. Replies: 2
    Last Post: 09-11-2002, 05:00 PM
  5. Homework help
    By Jigsaw in forum C++ Programming
    Replies: 2
    Last Post: 03-06-2002, 05:56 PM