如何在 Java 中递归处理此问题？

Question

在这个程序中，我需要从用户那里获得指示数字长度的输入：数字应该是素数，如果你从右边删除每个数字，剩下的数字应该仍然是素数.即 2399 就是这样一个数字。因为2399是素数，还有239、23、2。所以如果输入是3，所有这个长度和这个质量的数都应该打印出来。我有一个简单的代码，但它对于长度大于 4 的整数来说工作起来太慢了。

已编辑：实际上，这些数字中的每一个都是由先前设置的较小长度的数字组成的，即{2,3,5,7}通过将每个数字加1位并检查数字是否生成的是素数还是非素数

这将产生下一组数字{23,29,33,...} 这就是为什么我正在寻找递归解决方案，以防止在主 class 中进行线性搜索，这会使程序太慢。

import java.util.*;

public class Main {

    public static boolean isPrime(int n) {
        for (int i = 2; i < n; i++)
            if (n % i == 0)
                return false;
        if(n==1)
            return false;
        return true;
    }

    public static int digitCount(int n){
        int count = 0;
        while(n!=0){
            n /= 10;
            ++ count;
        }
        return count;
    }

    public static int countPrimesubnum(int n) {
        int count = 0;
        while(n>0) {
            if(isPrime(n) == true){
                count ++;
            }
            n/=10;
        }
        return count;
    }

    public static void isWanted(int n){
        if (countPrimesubnum(n) == digitCount(n))
            System.out.println(n);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a = (int)Math.pow(10,n-1);
        int b = (int)Math.pow(10,n);
        int c = b-1;
        for (int i=a; i<c; i++){
            isWanted(i);
        }
    }

}

Answer 1

首先阅读primality tests. The simplest method described is trial division，你用的是什么，不过差不多。要检查的最大数量是 square root of n，而不是 n - 1。像这样实现它，你会看到性能的显着提升。

如果速度还是不够，可以进一步优化：

保留素数缓存，因为您目前正在多次检查一个数的素数
同样在这一行 - for (int i = 2; i < n; i++)，你只需要检查其他素数，而不是每个数字
您可以在循环之前添加 even/odd 检查，even 数字永远不是质数，只有 odd 可能是。

提到的所有这些优化都会提高性能，尤其是第一个。正如回答 here.

那样，肯定不会使用递归

Answer 2

单独使用递归对你帮助不大。您需要的是重用您已经计算出的值。为此，您可以使用递归。首先，正如其他人已经提到的，您应该重写 isPrime 函数以仅在 2 到 sqrt(n). 之间迭代这样做会稍微提高您的性能。

但是回到你的计算问题，如果确切的数字是质数或不是质数！想象一下，如果您要搜索 3 位数字。例如，您应该计算 23 是否为质数 11 次。但是如果你想搜索 4 位数字，你必须调用数字 23 的 isPrime 函数超过 100 次，这将大大降低你的性能。

我的方法是从你所拥有的东西开始构建来解决这个问题。我会用你想要的长度 n-1 的特征来计算所有素数，并在末尾添加数字 1, 3, 7, 9 。这样，每个数字只使用一次 isPrime 函数。

这是我的方法和你的方法在我的本地机器（MacBook Pro 2019）上的性能比较。在这两种情况下，我都使用了相同的 isPrime 函数：

n	Your Execution time	My Execution Time
3	2 mili seconds	14 mili seconds
4	5 mili seconds	14 mili seconds
5	18 mili seconds	14 mili seconds
6	248 mili seconds	14 mili seconds
7	5.5 seconds	14 mili seconds
8	2 minutes and 32 seconds	15 mili seconds
9	didn't get an answer after 30 minutes	14 mili seconds.

如您所见，当输入变大时，我的代码的执行时间变化不大，但随着输入变大，您的性能会急剧下降。

我附上了我们的两个代码，因此您的代码比较了性能。它是用 Kotlin 编写的，而不是 Java，以便在将其转换回 Java 时理解算法。要了解我所做的，您只需要看一下函数 findRecursivePrimes 和 findNewPrimes.

@ExperimentalTime
@JvmStatic
fun main(args: Array<String>) {
    val n: Int = 9
    val absoluteValueWithoutDP = measureTime {
        val a = 10.0.pow((n - 1).toDouble()).toInt()
        val b = 10.0.pow(n.toDouble()).toInt()
        val c = b - 1
        for (i in a until c) {
            isWanted(i)
        }
    }.absoluteValue
    val absoluteValueWithDP = measureTime {
        val allPrimesOfLenN: List<Int> = findRecursivePrimes(n)
        for (element in allPrimesOfLenN) {
            println(element)
        }
    }.absoluteValue
    println("run time of base algorithm : $absoluteValueWithoutDP")
    println("run time of improved algorithm : $absoluteValueWithDP")

}

private fun findRecursivePrimes(n: Int): List<Int> {
    val allPrimesOfLenN: List<Int> = if (n == 1) {
        listOf(2, 3, 5, 7)
    } else {
        val allPrimesOfLenNMinusOne = findRecursivePrimes(n - 1)
        findNewPrimes(allPrimesOfLenNMinusOne)
    }
    return allPrimesOfLenN
}

private fun findNewPrimes(allPrimesOfLenNMinusOne: List<Int>): List<Int> {
    var allPrimesOfLenN: List<Int> = emptyList()
    for (prime in allPrimesOfLenNMinusOne) {
        val primeTimesTen = prime * 10
        for (i in listOf(1, 3, 7, 9)) {
            val n = primeTimesTen + i
            if (isPrime(n)) {
                allPrimesOfLenN = allPrimesOfLenN.plus(n)
            }
        }
    }
    return allPrimesOfLenN
}

private fun isPrime(n: Int): Boolean {
    for (i in 2 until sqrt(n.toDouble()).toInt()) if (n % i == 0) return false
    return n != 1
}

fun digitCount(n: Int): Int {
    var n = n
    var count = 0
    while (n != 0) {
        n /= 10
        ++count
    }
    return count
}

fun countPrimesubnum(n: Int): Int {
    var n = n
    var count = 0
    while (n > 0) {
        if (isPrime(n)) {
            count++
        }
        n /= 10
    }
    return count
}

fun isWanted(n: Int) {
    if (countPrimesubnum(n) == digitCount(n)) println(n)
}

如何在 Java 中递归处理此问题？

How do I approach this recursively in Java?

java

recursion

primes