我的语法有什么问题吗？我这样做是否有效？

Question

我正在尝试创建一种方法来告诉我天气或数字是否为素数是真是假。这是代码：

class prime
{

    public static boolean prime (int a, int b) 
    { 
        if (a == 0) 
        {
            return false; 
        }
        else if (a%(b-1) == 0) 
        {
            return false; 
        }
        else if (b>1) 
        {
            prime (a, b-1) ;
        }
        else
        {
            return true; 
        }

    }

    public static void main (String[] arg) 
    {
        System.out.println (prime (45, 45)) ; 
    }
}

当我尝试编译此代码时，我收到此错误消息：

prime.java:23: missing return statement
    }
    ^
1 error

我可能会误解错误消息的内容，但在我看来，没有缺少返回语句，因为我对每个可能的集合都有一个返回语句的条件。如果 a 为 0，则返回 false，如果不是，则检查 a 是否可被 b 整除，如果是，则返回，如果不是，则返回，如果 b 大于 1，则重新开始。如果 b 不大于 1，它也会返回。

• 而且看起来有点乱 使这个方法接受两个整数 是相同的 int。

• 我的语法有什么问题/为什么我收到错误消息？有没有一种方法可以使我在 main 中使用的方法只需要采用一个 int （也许另一种方法将该 int 拆分为两个克隆，然后将其传递给 public static boolean prime ？

• 或者是否有更有效的方法？ 正在做我想念的事情 完全吗？

Answer 1

在您的 prime 函数中，有四种可能的代码路径，其中之一不返回任何内容。这就是错误消息所抱怨的内容。 您需要将: 替换

prime (a, b-1) ;

为

return prime (a, b-1) ;

在 else if (b>1) 情况下，

: 。话虽如此，这实际上并不是计算一个数是否为素数的好方法。问题是每个递归调用都会分配一个堆栈帧，如果您试图计算 99,999,999 是否是质数，您将遇到严重的堆栈溢出问题？

对于某些问题来说，递归是一个非常好的工具，但您需要了解堆栈深度。至于更有效的解决方案，您可以执行许多测试来确定一个数字不是质数，然后仅使用强力测试来检查其他数字。

您应该注意的一件事是首先检查较小数字的整除性，因为这会更快地缩小您的搜索范围。并且不要在可以使用乘法的地方使用除法，乘法通常更快（尽管并不总是如此）。

还有一些可能的狡猾技巧：除了

• 2 以外，所有以 2、4、6、8 或 0 结尾的数字都是非素数。
• 除 5 之外，所有以 5 结尾的数字都是非素数。
  仅这两条规则就会减少 60% 的搜索空间。假设您以字符串形式获取测试数字，那么即使在转换为整数类型之前测试该字符串的最后一位数字也是一件简单的事情。

可分割性检查有一些更复杂的规则。如果你取9的倍数并将所有数字相加得到一个新数字，然后对这个数字重复一遍，然后继续直到你有一个数字，你会发现它总是9。

这会给你另一个数字尽管检查时间更长，但搜索空间减少了 10%。请记住，这些检查仅对数量非常大的情况有利。对于 32 位整数来说，优势并不是那么大，因为预先计算的位图在那里会更有效（见下文）。

为了简单起见，我将使用以下迭代解决方案：

public static boolean prime (int num) {
    int t = 2;
    while (t * t <= num) {
        if ((num % t) == 0) {
            return false;
        }
        t++;
    }
    return true;
}

如果您希望代码具有真实速度，则根本不必每次都进行计算。计算一次以创建您感兴趣的范围内所有素数的位数组（其中一种筛选方法可以做到这一点），然后只需根据该位数组检查您的值即可。

如果您甚至不希望每次程序启动时计算数组的成本，请执行一次并将位数组保存到磁盘文件，并在程序启动时加载它。

实际上，我有一个文件中前 1 亿个素数的列表，对我来说，使用 grep 来查找一个数字是否是素数比运行一些代码来计算它更容易、更快捷:-)

---

至于为什么你的算法（用 return 语句修复）坚持认为 7 不是素数，它会坚持每个数字都是非素数（没有用负数进行检查）数字，我很确定它们会导致一些严重的问题 - 您的第一个检查可能应该是 if (a < 1) ...)。

让我们检查一下调用 prime(3,3) 时会发生什么。

第一次，它满足第三个条件，因此调用 prime(3,2)。

然后它满足第二条件，因为3 % (2-1) == 0为真（N % 1总是< /em> 0).

所以它返回 false。这可能可以通过将第三个条件更改为 else if (b>2) 来解决，尽管我还没有彻底测试过，因为我认为递归解决方案无论如何都不是一个好主意。

---

以下完整的代码片段将满足您的需要，尽管我很欣赏您想知道自己做错了什么的好奇心。这是一个真正能成为优秀代码切割者的标志。

public class prime
{
    public static boolean isPrime (int num) {
        int t = 2;
        while (t * t <= num) {
            if ((num % t) == 0) {
                return false;
            }
            t++;
        }
        return true;
    }


    public static void main (String[] arg) 
    {
        System.out.println (isPrime (7)) ; 
    }
}

Answer 2

您似乎有这样的印象：因为递归最终会找到一个将命中 return 语句的基本情况，所以该返回将通过所有递归调用冒泡。那不是真的。每个递归调用必须传递如下结果：

return prime(a, b - 1);

Answer 3

如果 b 大于 1，您的函数将不会返回任何内容。

可能是 return prime (a, b-1) ; 吗？

Answer 4

为了提高效率，多考虑一下自己的条件。您真的需要测试从 2 到 N 的每个因素吗？是否有不同的停止点可以帮助素数测试更快地完成？

为了制作更好的 API，请考虑将递归方法设为私有，并使用有助于引导该过程的公共入口点。例如：

public static boolean prime(int n) {
  return recurse(n, n);
}

private static boolean recurse(int a, int b) {
 ...
}

将方法设置为私有意味着不能从其他类调用它。对于该类的用户来说，它实际上是不可见的。这里的目的是通过提供公共帮助器方法来隐藏“丑陋”的额外参数。

考虑一些合数的因数。 10 因数为 5×2。 12 因数为 6×2。 14 因数为 7×2。现在考虑 5×5 的 25. 25 个因数。 9呢？你看到一个模式了吗？顺便说一句，如果这不是家庭作业，请告诉我。这种说教对我来说很难。

Answer 5

为了回答为什么 7 不起作用，假设你是计算机并通过你的逻辑进行工作。这是你写的。

class prime
{

    public static boolean prime (int a, int b) 
    { 
        if (a == 0) 
        {
            return false; 
        }
        else if (a%(b-1) == 0) 
        {
            return false; 
        }
        else if (b>1) 
        {
            // Have to add the return statement
            // here as others have pointed out!
            return prime(a, b-1);
        }
        else
        {
            return true; 
        }

    }

    public static void main (String[] arg) 
    {
        System.out.println (prime (45, 45)) ; 
    }
}

所以让我们从 7 开始

if(7 == 0) // not true, don't enter this block
else if(7 % 6 == 0) // not true
else if(7 > 1) // true, call prime(7, 6)

if(7 == 0) // not true, don't enter this block
else if(7 % 5 == 0) // not true
else if(6 > 1) // true, call prime(7, 5)

if(7 == 0) // not true, don't enter this block
else if(7 % 4 == 0) // not true
else if(5 > 1) // true, call prime(7, 4)

......继续调用 prime(7, 2)

if(7 == 0) // not true, don't enter this block

else if(7 % 1 == 0) true, return false

当你继续调用 prime(n, 2) ，它总是会返回 false，因为你有逻辑错误。

Answer 6

您的递归方法必须返回一个值，以便它可以展开。

    public static boolean prime (int a, int b) 
{
    if (a == 0) 
    {
        return false; 
    }
    else if (a%(b-1) == 0) 
    {
        return false; 
    }
    else if (b>1) 
    {
        return prime (a, b-1) ;
    }
    else
    {
        return true; 
    }

}

我可能会以不同的方式编写它，但这就是您无法编译代码的原因。

Answer 7

我认为原来的问题已经得到解答 - 您需要在 else if (b>1) 的正文中插入 return - 我只是想指出您的代码仍然当给定 1 作为 b 的值时，将会崩溃，并抛出 ArithmeticException，因为 a%(b-1) 将被计算为 a%0 ，导致被零除。

您可以通过创建第一个 if 语句 if (a == 0 || b == 1) {} 来避免这种情况
这不会改善程序查找素数的方式，它只是确保少一种导致程序崩溃的方法。

Answer 8

与@paxdiblo的答案类似，但效率稍高一些。

public static boolean isPrime(int num) {
    if (num <= 1 || (num & 1) == 0) return false;
    for (int t = 3; t * t <= num; t += 2)
        if (num % t == 0)
            return false;
    return true;
}

一旦确定该数字不为偶数，则可以跳过所有偶数。这将使需要检查的数量减半。