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

Bob John
  • 3,688
  • 14
  • 43
  • 57
  • 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 '12 at 21:08

4 Answers4

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.
}
stefan
  • 10,215
  • 4
  • 49
  • 90
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++;
    }
}
Luchian Grigore
  • 253,575
  • 64
  • 457
  • 625
  • 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 '12 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 '12 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;
    }
}
NominSim
  • 8,447
  • 3
  • 28
  • 38
  • Surely that would just get stuck in a loop when it reaches a divisor? –  Aug 16 '12 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 '12 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 '12 at 20:54
  • @eq- I did it this way to maintain the "typical" for loop structure. – NominSim Aug 16 '12 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;
}
Micah
  • 452
  • 4
  • 8