找出所有只能被 3、5 和 7 整除的数字

Question

我在一次采访中被要求找出所有只能被 3、5 和 7 整除的数字。我的目的是我们可以像

这样进行检查

if (num%3==0 || num%5==0 || num%7==0) 
  return true 
else 
  return false.

但在这种情况下，如果我们有 6，它将通过测试，但它也可以被 2 整除，所以这不起作用。你能有目的吗？我正在使用 java。查找意味着检查某个数字是否只能被这个数字整除

Answer 1

我不会给你一个 Java 算法，因为它应该很容易实现。

您可以：

1. check if (n%3 == 0)
2. if it is, set n /= 3 and repeat step 1.
3. do the same for the number 5 and 7
4. now if n != 1, return false, else return true

在Java算法中：

// n is some random natural number
if (n == 1 || n == 0)
    return false

while (!n%3) 
{
    n /= 3;
}
while (!n%5)
{
    n /= 5;
}
while (!n%7)
{
    n /= 7;
}
if (n == 1)
{
    return true;
}
else
{
    return false;
}

这不是最好的语法，我只是给出上述算法的直接实现。

Answer 2

我会通过从原始数字中删除所有 3、5 和 7 的因数，然后看看还剩下什么来解决这个问题。

while(num % 3 == 0)
{
    num = num / 3;
}
while(num % 5 == 0)
{
    num = num / 5;
}
while(num % 7 == 0)
{
    num = num / 7;
}

return (num == 1);

Answer 3

我们首先注意到1是集合的成员。虽然它不能被 3、5 或 7 整除，但它也不能被除 3、5 或 7 以外的任何数整除，所以我们说 1 在集合中。这符合集合的数学定义 { x = 3ⁱ · 5^j · 7^k | i, j, k ≥ 0 }.

一种方法是从 1 开始计数，每一步加 2，然后检查数字是否只能被 3、5 和 7 整除。这很慢，因为它做了很多立即被丢弃的工作，因为有只能被 3、5 和 7 整除的数字比奇数少得多。

更好的方法是通过归纳法直接生成所需的数字。数字1在集合中，对于集合中的任何x，3x、5x[=也是34=] 和 7 x。因此，生成所有只能被 3、5 和 7 整除的数字的算法依次为：

1. Initialize a priority queue with the number 1. 2. Pop the smallest number in the priority queue, call it x. 3. Add 3x, 5x and 7x to the priority queue. 4. Output x as the next integer in the set. 5. If you want more output, go to Step 2. 6. Halt.

我实现了这两种算法；你可以在 http://ideone.com/YwnAQ8. The brute-force method takes a little over ten seconds to find the 203 members of the 3,5,7 set less than a million; the priority queue does the same calculation in a hundredth of a second, a thousand times faster. The priority queue implementation used there is explained at my blog. You can also see the set of 3,5,7 numbers at OEIS.
看到它们

找出所有只能被 3、5 和 7 整除的数字

Find all numbers only divisible by 3, 5 and 7

math

division