0

我正在用Java开发一个素数分解程序，它显示一个数字的所有素数，即使它们重复。我有这个：

public static void factors(int a)
{
    int c=1;
    for(int i = 1; i <= a;i++)
    {
        if(a%i == 0)
        {
            for(int k = 2; k < i; k++)
            {
                if(i%k == 0)
                {
                    c = 1;
                    break;
                }
                else
                {
                    c = 0;
                }
            }
            if(c == 0 || i == 2)
            {
                System.out.print(i+ ", ");
            }
        }
    }
}

我需要考虑重复因素（如 2、2、2 中的 8）。如果不完全重组，我怎么能做到这一点？

4

3 回答 3

1

我认为你应该重新开始，并从这个简单的描述中构建一个算法：

  • 准备一个List<Integer>小于或等于 2^16 的素数
  • 从低到高遍历这个列表，依次尝试每个素数作为候选除数
  • 每次遇到工作除数时，不断地把它除掉，直到不能再除此数为止；然后继续下一个素数
  • 一旦你到达素数列表的末尾，你的剩余数字也应该被打印出来，除非它等于1.

查找素数列表本身就是一个有趣的问题。早在 1972 年，Dijkstra 就写了一篇引人入胜的章节。这篇文章有一个 C++ 实现和一个非常好的讨论。

于 2012-03-24T19:28:57.717 回答
0

(1)if(c == 0 || i == 2) 错误，它也会打印2。a == 5

(2) 为了在不更改代码 (*) 的情况下执行您所要求的操作 - 您应该计算每个素数因子可被数字整除的次数。只需在您的打印语句[伪代码]之前添加一个新循环即可完成：

boolean b = true;
int k = 1;
while (b) { 
  if (a % (int) Math.pow(i, k+1) == 0) k++;
  else b = false;
}

在这个循环结束时，k 表示有多少次i是 的素数a。

(*) 注意：虽然这种方法应该可行，但我仍然会使用@KerrekSB 的建议进行重新设计。

于 2012-03-24T19:36:04.300 回答
0

您可以拥有另一个集合来维护因子及其计数，并最终可以解释重复的因子。一张有计数的地图是我的选择。

于 2012-03-24T19:25:50.503 回答