3

我需要对一系列数字进行排序。数字可以从 0 到 1000。用户输入的数字范围在 0 到 1000 之间。因此，例如，如果他们可能输入 0 -> 500。

我的目标是获取给定范围内的所有数字，并输出该范围内只有 4 个可能除数的所有数字（包括 1 和它本身。

我想知道我是否应该使用这样的算法，或者我是否应该检查和 int 数组，其中包含 1 - 1000 可被 4 整除的所有数字（因此该数组没有 1-1000 它有该范围内的数字只能被整除 4 次。需要手动工作才能将所有可能的除数添加到该数组中）。

我希望让它变得高效，只是我不确定使用这样的算法是否会非常快。

4

1 回答 1

6

您正在寻找一个数字，它是两个素数的乘积编辑：或素数的立方。由于您的数字很小，您可以制作一个 2 到 500 之间素数的简短表格。然后，从 2 开始，将每个素数乘以它上面的每个素数，直到超过上限。

编辑：这是作业吗？如果是的话，我可能已经说得太多了。如果不是，如果我的答案没有意义，我可以提供一些代码或伪代码。

编辑：谢谢，Daniel Fischer：我错过了素数的立方体。您可以检查这些并将其包含在您的外部循环中。（在将素数乘以它上面的每一个之前，看看它的立方体是否在所需的范围内。）

一般来说：

for ( p1 is a prime in your list, except for the last) {
    if p1 cubed is in your range, add it to the answer
    for (p2 is a prime in your list greater than p1) {
        if p2*p1 is in your range, add it to the answer
        //optimization: break when you know you won't find any more
    }
}
// optimization: calculate the ranges of p1 and p2 to be included 
// before you start each loop
// (probably only worthwhile if you raise the limit to something 
// much larger than 1000)

对于这种规模的数字，它肯定足够快。我在一毫秒内就完成了（找到 0 到 1000 之间的 292 个数字。我使用了硬编码的素数——对于这个输入范围，你只需要其中的 95 个。）

于 2012-04-22T17:36:02.377 回答