2

Can someone help correct my algorithm? I've tested it on a few numbers, and it doesn't output the complete factorization. For numbers with a large number of factors, it just completely fails.

int num = 20;

for(int i = 2; i <= num; i++)
{
    if(num%i == 0)
    {
        cout << i << endl;
        cout << num << endl;
        num = num/i;    
    }
}

EDIT: The two answers provided did not work, still not getting full results.

EDIT2: Divisors VS Factors

1
  • 2
    just as a side note: please try to be more precise in the future. First of all, it's not "inaccurate", it's incomplete results. Try adding expected output for an example (such as "if 15 is the input, the ouput should be 1,3,5,15, but i only get ..."). You don't need to edit to say that the answers aren't what you want, there's a comment section below each answer for exactly that purpose. Don't get me wrong: Your question is good, but with a little more effort you can make it easier for everyone to understand what you want and you will get better answers!
    – stefan
    Aug 16, 2012 at 21:08

4 Answers 4

12

Judging from you comment to @Luchian Grigore, you're confusing divisors with (prime) factorization. Divisors of a number are all numbers for which num % i == 0 is true. Factorization means getting a representation of num by a product of smaller numbers. If you want uniqueness of factorization, you usually use prime factorization.

To get all the divisors your code should be

for ( int i = 1; i <= num; ++i ) // note that 1 and num are both trivially divisors of num
{
    if ( num % i == 0 ) // only check for divisibility
    {
        std::cout << i << std::endl;
    }
}

to get the (prime) factorization, it's

for ( int i = 2; i <= num; ++i )
{
    while ( num % i == 0 ) // check for divisibility
    {
        num /= i;
        std::cout << i << std::endl;
    }
    // at this point, i cannot be a divisor of the (possibly modified) num.
}
2

The problem is that you're increasing i even if it is a divisor, and you shouldn't unless you find all its occurences.

So, for 4, you'd have 2 twice. But after the first 2 you encounter, you exit the loop because i is incremented to 3 and num became 2.

The following should work:

for(int i = 2; i <= num; )
{
    if(num%i == 0)
    {
        cout << i << endl;
        cout << num << endl;
        num = num/i;    
    }
    else
    {
        i++;
    }
}
2
  • Hi, thank you for the response. I c/p this into my code and I'm still not getting accurate results. For the number 378, which has 16 factors, I'm only getting back 10, 2 of which are spit out twice (3&7).
    – Bob John
    Aug 16, 2012 at 20:45
  • 2
    @BobJohn, the number 378 has 16 divisors, but only 5 factors (3 discinct). Finding divisors is a different problem.
    – eq-
    Aug 16, 2012 at 20:52
1
for(int i = 2; i <= num; i++)
{
    if(num%i == 0)
    {
        cout << i << endl;
        cout << num << endl;
        num = num/i;    
        i--; // Add this to account for multiple divisors
    }
}

for(int i = 2; i <= num; i++)
{
    if(num%i == 0)
    {
        cout << i << endl;
        cout << num << endl;
    }
}
4
  • Surely that would just get stuck in a loop when it reaches a divisor?
    – user1486147
    Aug 16, 2012 at 20:43
  • This doesn't work. It gives me the same results as the other answer, but it doesn't give me all of the factors.
    – Bob John
    Aug 16, 2012 at 20:52
  • 1
    @BobJohn This gives out all of the factors, it looks from your comments that you are looking for all divisors, I'll edit my answer with that.
    – NominSim
    Aug 16, 2012 at 20:54
  • @eq- I did it this way to maintain the "typical" for loop structure.
    – NominSim
    Aug 16, 2012 at 20:56
0

This should work. Note, should use c++11 for move constructor, otherwise you are going to want to pass in a std::list& instead.

std::list<int64_t> factor(int64_t f)
{
    std::list<int64_t> factors;
    for(int64_t ii = 2; ii<=f; ii++) {
        while(f % ii == 0) {
            f = f/ii;
            factors.push_back(ii);
        }
    }

    return factors;
}
1
  • Most C++98 compiles do have RVO. Also should really be using a std::vector not a std::list in general. Aug 22, 2015 at 7:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.