Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

C++ : Program that gives u the prime factors!

  1. May 20, 2010 #1
    i need help making a program that only displays the prime factors
    ex: 100 = 2*2*5*5

    i got the program to display all the factors but after that im lost.

    here is the code so far
    oh its in C++

    #include <iostream>

    using namespace std;

    int main()
    {
    cout << "Enter a number: ";
    int num;
    cin >> num;
    int i,k = 0;

    for (int i=2; i <= num; i++)
    {
    if( num % i == 0)
    {
    if(num % i == 0)
    {
    k = num / i;
    }
    cout << i << " " << k << endl;
    }
    }
    return 0;
    }
     
  2. jcsd
  3. May 20, 2010 #2
    Try to do this slightly differently:

    Code (Text):

    #include <iostream>

    using namespace std;

    int main()
    {
    cout << "Enter a number: ";
    int num;
    cin >> num;

    for (int i=2; i <= num; i++)
    {
     while(num % i == 0)
     {
       num /= i;
       cout << i << " ";
     }
    }
    cout << endl;
    return 0;
    }
     
     
    Last edited: May 21, 2010
  4. May 20, 2010 #3
    any certain direction i should go in?
     
  5. May 20, 2010 #4
    I don't understand your question.
     
  6. May 20, 2010 #5
    im not sure on how to go about changing it. any advice?
     
  7. May 21, 2010 #6
    Do you see the code in my post?
     
  8. May 21, 2010 #7
    oh sorry my mistake. i ended up doing a while loop then a for loop inside, but thank you for the help
     
  9. May 21, 2010 #8

    Mark44

    Staff: Mentor

    Something to keep in mind is that you don't have to check all of the integers from 2 to num. It is sufficient to go up to sqrt(num) - or the largest integer greater than or equal to sqrt(num). The idea is that if num has a factor smaller than sqrt(num), then there will be one larger than sqrt(num) as well.

    For example, suppose num is 85. All you need to do is check the integers from 2 though 9.

    Check 2 - not a divisor.
    Check 3 - not a divisor.
    Check 4 - not a divisor.
    Check 5 - is a divisor. (The other divisor is 17.)
    Check 6 - not a divisor.
    Check 7 - not a divisor.
    Check 8 - not a divisor.
    Check 9 - not a divisor.

    FYI, you don't actually need to check 4, 6, 8, 10, etc. If 2 is not a divisor, then no other even integer will be a divisor. The same is true for 6, 9, 12, etc. If 3 isn't a divisor, then neither will any other multiple 3 be a divisor. There are lots of ways to make the program more efficient, but they add complexity to the code.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: C++ : Program that gives u the prime factors!
  1. C program-prime (Replies: 6)

  2. C programming (Replies: 9)

Loading...