Поиск факторов числа. Не получать точные результаты

Может кто-то помочь исправить мой алгоритм? Я тестировал его на несколько номеров, и он не выводит полную факторизацию. Для чисел с большим числом факторов он просто полностью терпит неудачу.

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

EDIT: два предоставленных ответа не сработали, все еще не получая полных результатов.

EDIT2: Divisors VS Factors

Судя по вашему комментарию к @ Luchian Grigore , вы вводите в заблуждение делителей с (простой) факторизацией . Дивизорами числа являются все числа, для которых num % i == 0 истинно. Факторизация означает получение представления num продуктом меньших чисел. Если вы хотите уникальность факторизации, вы обычно используете простую факторизацию.

Чтобы получить все делители, ваш код должен быть

 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; } } 

для получения (первичной) факторизации, это

 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. } 

Проблема в том, что вы увеличиваете i даже если это делитель, и вы не должны, если не найдете все его вхождения.

Итак, для 4, у вас будет 2 раза два. Но после первых 2 вы сталкиваетесь, вы выходите из цикла, потому что i увеличивается на 3, а num 2.

Следующее должно работать:

 for(int i = 2; i <= num; ) { if(num%i == 0) { cout << i << endl; cout << num << endl; num = num/i; } else { i++; } } 
 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; } } 

Это должно сработать. Заметьте, должен использовать c ++ 11 для move constructor, иначе вы захотите перейти в std :: list & вместо этого.

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