Thread: Prime Factor Fxn

  1. #1
    Registered User
    Join Date
    Nov 2002
    Posts
    1,109

    Prime Factor Fxn

    I need some help with the prime_factor fxn. I think I'm just missing something easy that I'm not seeing right now. Anyways, it's supposed to output the prime factors of an input number.

    When I input 12, it outputs the desired results; however, if I enter in another nonprime number, it doesn't output the desired results. For example, if I input 6, it only says that 2 is a factor, but does not say 3 is a factor.

    Ex. Output:

    Enter an integer < 1000 -> 12

    The prime factorization of the number 12 is:
    2 is a factor
    2 is a factor
    3 is a factor
    ______________________

    Enter an integer < 1000 -> 6

    The prime factorization of the number 6 is:
    2 is a factor

    // It doesn't output that 3 is also a factor for the number 6.

    Here's an example main to go with the program, followed by the function I need help with:

    Code:
    #include <iostream>
    #include <string>
    #include <cmath>
    using namespace std;
    
    const string SPACE_STR = "   ";
    
    void prime_factor(int number);
    bool is_prime(int number);
    
    int main() {
       int number;
    
       cout << "Enter a number < 1000 -> ";
       cin >> number;
    
       prime_factor(number);
    
       return 0;
    }
    
    // Function I need help with.
    
    void prime_factor(int number)
    {
       bool isPrime = is_prime(number);
       int prime = number;
       int i = 2, j;
       double squareRoot = sqrt(static_cast<double>(number));
    	int count = 0;
       
       cout << "The prime factorization of the number " << number << " is:" << endl;
    	
    	if(isPrime)
          cout << SPACE_STR << number << " is a prime number." << endl;
       else {
          while((prime > 0) && (i <= squareRoot)) {
             if((prime % i) == 0) {
    				count++;
    				for(j = 0; j < count; j++)
    					cout << SPACE_STR;
                cout << i << " is a factor" << endl;
                prime /= i;
    			} else         
             	i++;
          }
       }
    }
    
    bool is_prime(int number)
    {
       int i;
       
       for(i = 2; i < number; i++) {
          if((number % i) == 0)
             return false;
       }
       
       return true;
    }
    Last edited by alpha; 10-20-2003 at 10:59 PM.

  2. #2
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    your C++ code seems alright, but you have a logic flaw.

    if number is 6
    then sqrt of 6 is less than 3 and greater than 2 so squareRoot is something between 2 and 3, although I don't know exactly what it is.

    6 is not prime so you end up going into this loop
    Code:
    while((prime > 0) && (i <= squareRoot)) 
    {
             if((prime % i) == 0) 
            {
                cout << i << " is a factor" << endl;
                prime /= i;
            } else         
                i++;
    }
    the initial time through the loop prime = 6, i = 2;
    prime % 2 equals 0 so the output is done and
    prime is divided by 2 to get 3

    then you go back to the while conditionals a second time
    prime is 3 so it is > 0 and i is still 2 so it is <= squareRoot. Alls ok so far and you go into the if conditional where
    3 % 2 is not 0 so the if conditional is false and you end up at else where i is increased from 2 to 3.

    then you go back to the while conditionals a third time.
    prime is still 3 so it is > 0 but now i is 3 and it is greater than squareRoot so the while conditional fails and you don't get to the if(prime % i == 0) part that would say 3 is prime and therefore 3 will not be recognized as a prime factor and it won't be printed out for you.

    There are several ways to correct this logic so I'll let you have at it.

  3. #3
    Registered User
    Join Date
    Nov 2002
    Posts
    1,109
    wow, I just changed the i <= squareRoot to i <= number and it works. It makes more sense now too. I got confused at where nonprime numbers have a factor below their square root.

    Thanks for explaining it for me.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Calculating prime factor of a huge number.
    By Bakster in forum C Programming
    Replies: 15
    Last Post: 02-20-2009, 12:06 PM
  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. Prime Wonder
    By vasanth in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 10-07-2002, 11:49 PM
  5. Homework help
    By Jigsaw in forum C++ Programming
    Replies: 2
    Last Post: 03-06-2002, 05:56 PM