CODEWITHSUNDEEP
c++primesprime-factoring
Keaton Pennells
Keaton Pennells

Reputation: 199

finding prime factors of a given number c++ without functions

I need to find the prime factors of a number that the user inputs

Example:

Enter a number : 1430. The prime factors of 1430 are 2,5,11,13

I would prefer not using a function as I haven't covered it yet

Here is my code 

#include <iostream>
#include <iomanip>
#include <cmath>

using namespace std ;

int main () 
{
    int count, i , i2 ;
    int userInput, prime ;
    bool flag = false ;

    cout << "Enterr: " ;
    cin >> userInput ;
    cout << "The prime factors are: " ;
    for (i = 2; i < userInput ; i++)
    {
        if (userInput % i == 0) // this for loop is to check is the counter (i) is a multiple of userInput
        {   
            prime = i;
            // the next for loop is to check is the multiple is a prime number
            for( i2 = 2; i2< ceil(sqrt(prime))  ; i2++)
            {
                if (prime % i2 == 0)
                    flag = true ;
            }
        }
        if (flag == false ) 
            cout << i << ", "  ;
        flag = false ;
    }

    cout<< endl ;

    return 0 ;
}

My output completely ignores the second loop and just outputs all integers less than userInput

I was able to create a piece of code that checks if a number is a prime number here :

#include <iostream>
#include <iomanip>
#include <cmath>

using namespace std ;

int main () 
{
    int userInput, prime ;
    int i ;
    bool flag = false ;

    cin >> userInput ;

    for( i = 2; i < static_cast<int>(sqrt(userInput) + 1) ; i++)
    {
        if (userInput % i == 0)
            flag = true;        
    }

    if (flag == false ) 
        cout << "Number is a prime" << endl ;
    else
        cout << "Number is not a prime " << endl ;

    return 0 ; 
}

Sorry if there are any errors. I'm still a beginner at C++

Upvotes: 2

Views: 4790

Answers (3)

Will Ness
Will Ness

Reputation: 71119

you don't need to test for primality the divisors you find, if you divide them out of your number as you find them, while enumerating the candidates in ascending order:

    for (i = 2; i <= userInput/i;  )
    {
        if (userInput % i == 0) 
        { 
            cout << i << ", ";   // i is a prime factor of the original
            userInput /= i;      //   number in userInput
        }
        else
            ++i;
    }
    if (userInput > 1)
    {
        cout << userInput;       // the biggest prime factor of the original
    }                            //   input number

Thus found prime factors of the input number are printed out in ascending order as well.

Upvotes: 1

Frank Schmitt
Frank Schmitt

Reputation: 30835

You're almost there - you just need to move this block

  if (flag == false )
          cout << i << ", "  ;
      flag = false ;

into your 

if (userInput % i == 0)

block (you only want to print numbers that are divisors of your input number), and everything should be fine.

Upvotes: 3

Nobody moving away from SE
Nobody moving away from SE

Reputation: 9555

Did you try to debug (even mentally) what is happening in your program? I doubt so or you would have noticed following:

if (userInput % i == 0)

will be false for all divisors. This means you will directly go to the check 

if (flag == false )

which is true as you did not change flag to true and hence you wrongly give the number as prime factor.

You also should consider corner cases. For example the prime factors of a prime are only the prime itself (which you can never output as you never reach it (i < userInput;)

Regarding your no function restriction: You cannot avoid functions or your code won't do anything. You can however avoid things that look like function calls (looking like name()).

To eliminate sqrt and ceil you should rearrange the condition to i2 * i2 <= prime

Upvotes: 0

Related Questions