java - 我的语法有什么问题，我这样做效率高吗？

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，它也会返回。

• 而且不得不这样做似乎有点乱 让这个方法接受两个整数 是相同的整数。

• 我的语法有什么问题/为什么我会收到错误消息？有没有办法让我在 main 中使用的方法只需要一个 int(也许另一种方法将该 int 分成两个克隆，然后传递给 public static boolean primeproper？

• 或者有没有更有效的方法 做我想念的事 完全？

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 是 总是 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)) ; 
    }
}