Вывод основной функции факторизации
Я сделал эту функцию, которая вычисляет простую факторизацию числа (n), полученного от пользователя. У меня проблемы с ним из-за того, что он не печатает один и тот же фактор более одного раза.
Например:
Премфакторизация 3960 это:
11 5 3 3 2 2 2
Однако моя программа только распечатывает:
11 5 3 2
Может ли кто-нибудь помочь мне определить причину и найти решение?
void primefact(int n)
{
Stack f;
assert(n >= 0);
bool prime;
for(int d = 2; d <= n; d++) // Test for factors > 1
{
if(n % d == 0)
{
prime = true;
for(int j = 2; j < d; j++) // Test for prime
{
if(d % j == 0) // It is not prime
prime = false;
}
if(prime)
f.push(d);
}
}
while(!f.empty())
{
cout << f.top() << endl;
f.pop();
}
}
Решение
Простейший код для простой факторизации: —
for ( int i = 2; i <= num; ++i )
{
while ( num % i == 0 )
{
num /= i;
std::cout << i << std::endl;
}
}
Другие решения
Вы должны циклически повторять одно и то же простое число, если оно разделяет входные данные.
Может ли кто-нибудь помочь мне определить причину?
Вы проверяете, n делится на d, но затем вы переходите к следующему значению. Если n делится на d а также d прост, вам нужно на самом деле делить n от d и проверить d снова.
Давайте возьмем 12 в качестве примера. Основные факторы [3, 2, 2], Ваш код делает это:
n = 12, d = 2
n % d == 0? Yes. Push d. d = d + 1
n % d == 0? Yes. Push d. d = d + 1
n % d == 0? No. d = d + 1
n % d == 0? No. d = d + 1
n % d == 0? No. d = d + 1
n % d == 0? No. d = d + 1
// and so on until d == n
Вы хотите код, который делает это:
n = 12, d = 2
n % d == 0? Yes. Push d. n = n/d // n is 6, d is 2
n % d == 0? Yes. Push d. n = n/d // n is 3, d is 2
n % d == 0? No. d = d + 1 // n is 3, d is 3
n % d == 0? Yes. Push d. n = n/d // n is 1 so you're done
Вы, наверное, сами знаете, что ваш алгоритм далеко не оптимален. Так что это не сильно повредит производительности. замещать
if(prime)
f.push(d);
с
if (prime)
{
for (int d1 = d; n % d1 == 0; d1 *= d)
f.push(d);
}