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

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

我可能会错误地解释错误消息的内容,但在我看来,由于我对每个可能的条件都有一个return语句,因此没有丢失的return语句.如果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;
}

如果您想在代码中获得真正的速度,请不要每次都计算它.计算一次,在您感兴趣的范围内创建所有素数的位数组(其中一个筛选方法将执行此操作),然后只需根据该位数组检查您的值.

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

我实际上有一个文件中前100万个素数的列表,我用它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)) ; 
    }
}

Answer 2

你似乎有这样的印象,因为递归最终将找到一个基本案例,它将触及一个return语句,然后该返回将在所有递归调用中冒出来.这不是真的.每个递归调用必须传递出如下结果:

return prime(a, b - 1);