素数分解函数输出

-1

我做了这个函数，它计算从用户获得的数字（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(); 
    } 
}

来源

2014-10-29 NinjaZ

这将是一个恒星* *时间，通过这段代码与调试器行走。 – WhozCraig 2014-10-29 19:52:54

-1

最简单的代码： -

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

来源

2014-10-29 19:52:29 ravi

这是分解问题的一个很好的解决方案，但并没有直接解决OP为什么给出的代码不起作用的问题。 – Caleb 2014-10-29 20:21:09

@NinjaZ：当然会的。只要做'f.push'而不是'cout <<' – 2014-10-29 23:05:41

只要分割输入，你必须遍历相同的素数。对于因式分解

来源

2014-10-29 19:51:59

谁能帮我找出原因？

您正在检查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

来源

2014-10-29 19:54:27 Caleb

所以，问题的原因是你只是检查每个数字来看*如果它是一个主要因素，对吧？但是，每当你找到一个主要因素时，你想用这个因子除以n，然后再次尝试相同的因子。在为您编写代码的过程中，我不确定如何更好地解释问题。 – Caleb 2014-10-29 21:02:59

你可能知道自己，你的算法是远远没有达到最佳。所以这不会对性能造成太大的影响。更换

if(prime) 
    f.push(d);

与

if (prime) 
{ 
    for (int d1 = d; n % d1 == 0; d1 *= d) 
     f.push(d); 
}

来源

2014-10-29 23:09:53

素数分解函数输出

回答

相关问题