In this program I need to get input from the user that indicates the length of the numbers with this quality: The number should be prime and if you delete each digit from the right the number that is left should still be prime. i.e. 2399 is such a number. Because 2399 is prime, and also 239, and 23, and 2. So if the input is 3, all the numbers with this length and this quality should be printed. I have a simple code but it works too slow for integers with a length greater than 4.

Edited: Actually each of these numbers is made from the previous set numbers with smaller length, i.e. {2,3,5,7} by adding 1 digit to each and checking if the number which is produced is prime or not.

This will produce the next set of numbers {23,29,33,...} That's why I'm looking for a recursive solution in order to prevent the linear search in the main class which is making the program too slow.

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

}

CodePudding user response：

First of all read on primality tests. The simplest method described is trial division, what you are using, but almost. The max number to check is square root of n, not n - 1. Implement it like this, and you will see dramatic increase in performance.

If speed is still not enough, you can make further optimizations:

1. Keeping a cache of primes, because you currently you are checking a number more than once for primality
2. Also in this line - for (int i = 2; i < n; i ), you need to check only other primes, not every number
3. You could add even/odd check before loop, even numbers are never prime, only odd might be.

All those optimizations a mentioned will lead to increase in performance, especially the first one. Using recursion certanly will not, as answered here.

CodePudding user response：

Using recursion alone won't help you a lot. What you need is to reuse the values that you have already computed. For this, you could use recursion. First of all, as others already mentioned, you should rewrite your isPrime function to iterate only between 2 to sqrt(n). Doing this will improve your performance a little bit.

But back to your problem with computing if the exact number is prime or not! Imagine if you want to search 3 digit numbers. For instance, you should compute if 23 is prime or not 11 times. But if you want to search 4 digit numbers, you have to call the isPrime function for number 23 more than 100 times, Which will drastically reduce your performance.

My approach is to build from what you have to solve this problem. I would compute all primes with the feature you want with length n-1 and add numbers 1, 3, 7, 9 at the end. This way, you only use the isPrime function once per number.

Here is the performance comparison between my approach and yours in my local machine(MacBook Pro 2019). In both cases, I used the same isPrime function:

As you can see, the execution time of my code doesn't change much when the input gets larger, but your performance drastically decreases with larger inputs.

I've attached both of our codes, so your code compares the performance. It is written in Kotlin, not Java, to understand the algorithm when converting it back to Java. To understand what I've done you just need to take a look at function findRecursivePrimes and 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)
}