素数，当反转时也是素数

Question

这是我几年前拍的对代码战争的挑战。任务是找到所有的素数，也是一个素数，当反转，即13 -> 31是这样一个数字。这仍然是“最佳实践”和“聪明”两大类别中最受欢迎的答案。对这段代码有什么改进或想法吗？请记住，在这样的代码挑战中，我总是尽量精简代码。

=>输出中的示例：

    backwardsPrime(2, 100) => [13, 17, 31, 37, 71, 73, 79, 97] 
    backwardsPrime(9900, 10000) => [9923, 9931, 9941, 9967] 
    backwardsPrime(501, 599) => []

代码：

public class BackWardsPrime {

    public static String backwardsPrime(long start, long end) {
        StringBuilder sb = new StringBuilder();
        while(start <= end){
            long rev = Long.parseLong(new StringBuilder(
            String.valueOf(start)).reverse().toString());
            if(start > 12 && isPrime(rev) && isPrime(start) && start != rev) 
                sb.append(start + " ");  
            start++;
        }
        return sb.toString().trim();
    }
    
    static boolean isPrime(long n) {
        if(n % 2 == 0) return false;
        for(int i = 3; i * i  <= n  ; i += 2) {
            if(n % i == 0)
                return false;
        }
        return true;
    }
}

Answer 1

正确的

名称类.

什么是“后区首级”？我没有头绪。我可以猜到什么是向后的素数；也许您需要更改类的大写！

我被告知名字是由编码挑战决定的，所以你不能为了你的挑战而改变它；但是我要离开这个评论站--所需的类名太可怕了。

名称变量正确.

这种情况令人困惑：

    if ( ... && start != rev)

这是否真的测试反向值是否与起始值不同？不是的！您正在使用起始值作为循环变量，并使用start++;不断地递增它。创建一个新的循环变量，并使用适当的循环。

    for(long candidate = start; candidate <= end; candidate++) {
        ...
    }  

减少工作

你似乎已经确定，任何一位数的质数，当向后读时，都不会与原来的不同，而10 & 12不是质数，11是相反的。因此，您只需要考虑大于12的值。这个优化应该在循环开始之前完成，以避免在每次迭代中测试条件的开销。

您还应该注意到，2是唯一的偶数素数，因此您不需要查看任何偶数。与其将开始值向上移动1，还可以通过递增2跳过甚至值。

    if (start < 13)
        start = 13;
    else if (start % 2 == 0)
        start += 1

    for(long candidate = start; candidate <= end; candidate += 2) {
        ...
    }

避免创建不必要的中间结果

考虑：

new StringBuilder(String.valueOf(start))

您正在传递一个整数到函数，该函数将其转换为字符串，然后返回该字符串。这个功能是如何工作的？然后将得到的字符串传递给StringBuilder的构造函数，以复制到工作区域。你需要那个中间线吗？

new StringBuilder().append(candidate)

StringBuilder.append(long)函数接受一个long值，并将其直接转换为StringBuilder中的字符串字符。这可能会更快。它甚至更短3个字符，同时使用更长的变量名称，所以它肯定更简洁！

另外，考虑一下sb.append(start + " ");。这会将start转换为字符串(再次)，向其添加" " (在内部使用另一个StringBuilder!)，然后将这个全新的字符串附加到sb。相反，你可以写：

sb.append(candidate).append(' ');

不需要构造和丢弃中间字符串。

避免无用工作

        long rev = ...;
        if(start > 12 && isPrime(rev) && isPrime(start) && start != rev) 
            ...

如果start不是素数，那么是否存在点计算rev？

    for(long candidate = start; candidate <= end; candidate += 2) {
        if (isPrime(candidate)) {
            long rev = ...;
            if (isPrime(rev) && candidate != rev)
                sb.append(candidate).append(' ');
        }
    }  

好多了。但是那个candidate != rev呢？这看起来是一个非常快速的测试，而且isPrime(rev)可能要慢得多。

    for(long candidate = start; candidate <= end; candidate += 2) {
        if (isPrime(candidate)) {
            long rev = ...;
            if (candidate != rev && isPrime(rev))
                sb.append(candidate).append(' ');
        }
    }

但是等等！candidate != rev有多少次是假的？很少吗？它可能得不到任何好处，而且这种变化甚至可能减缓程序的速度。永远都是侧写！

以简洁性为代价的

性能

在循环中构造一个新的StringBuilder可能是一项昂贵的操作。您可以在循环之外构造一个，并使用.setLength(0)方法清除它，用于下一个迭代：

    StringBuilder temp = new StringBuilder();

    for(long candidate = start; candidate <= end; candidate += 2) {
        if (isPrime(candidate)) {
            long rev = Long.parseLong(temp.append(candidate).reverse().toString());
            if (isPrime(rev) && candidate != rev)
                sb.append(candidate).append(' ');
            temp.setLength(0);
        }
    }  

主要优化

缩减搜索空间

在200-299,400-699和800-899范围内有多少个素数是可逆素数？在2000-2999,4000-6999,8000-8999的范围内怎么样？在20000-29999,40000-69999,80000-89999范围内有多少？诸若此类?

零。可逆素数不能从2，4，5，6或8开始，因为当反转时，这个数将被2或5整除，因此不会是素数。

以有效的方式实现这一观察肯定不会使代码简洁，但会大大加快它的速度。留给学生。

Eratosthenes

筛

您可能正在使用试用部门进行许多许多原始性检查。使用Eratosthenes的筛子来生成素数标志的BitSet可能更有意义。然后isPrime(candidate)变成一个简单的O(1)查找：prime.get(candidate)。

或者，如果维护BitSet of 10^{\lceil \log_{10}{end} \rceil}位过于内存密集型，则使用筛子生成素数直至\sqrt{10^{\lceil \log_{10}{end} \rceil}}，并使用只有这些素数的试用除法，以避免由奇数组合数(9、15、21、25、27、33、.)进行无意义的尝试除法。

Answer 2

这里可以应用的一个优化是:保留到目前为止在HashSet中发现的所有素数对。让我们看一看例子：

backwardsPrime(2, 100) => [13, 17, 31, 37, 71, 73, 79, 97] 

当我们点击数字13时，我们发现13和31都是素数->，将它们保存在集合中；

当我们点击31时，我们在我们的集合中查找这个数字，并且，因为它在那里，我们可以跳过这个数字。

编辑:实际上，我们可以更进一步存储我们发现的非素数。在上面的例子中:当我们点击19 (素数)，然后我们检查91，这不是素数。后来，当我们达到91，我们已经知道它不是素数。

Answer 3

• 在某个范围内迭代一些值确实需要一个for循环！尽管代码非常简单，但是当引用当前元素的变量不被称为start时，就更容易理解了。while (start <= end)也有点令人困惑。所以我更喜欢for (long i=start ; i<=end ; i++)。
• 我还将引入一个函数rev()，以便能够通过rev(i)引用i的反面。这样，您还可以将涉及StringBuilder的相当笨重的表达式移出主方法。{ StringBuilder b=新StringBuilder(String.valueOf( n) )；返回Long.parseLong(b.reverse().toString())；}
• 最后，isPrime中的优化使代码更难理解，也有点混乱(难道isPrime(2)不应该返回true吗？)我只会使用平方根优化i * i <= n，因为它可以大大提高效率，而不会增加太多的噪音。静态布尔值isPrime(long n) { for (int i= 2；i*i <= n；i++)如果(n%i == 0)返回false；返回true；}

考虑到这两个帮助程序，您可以将主要方法简化为这个非常小的版本：

public static String backwardsPrime(long start, long end) {
    StringBuilder sb = new StringBuilder();
    for (long i=start ; i<=end ; i++)
        if (isPrime(i) && isPrime(rev(i)) && i != rev(i)) 
            sb.append(i + " ");  
    return sb.toString().trim();
}