15
\$\begingroup\$

This is a challenge on Codewars I took years ago. Task is to find all prime numbers that are also a prime number when reversed, i.e. 13 -> 31 is such a number. This is still the answer with the most upvotes in the categories 'Best practice' as well as in 'Clever'. Any improvements or thoughts about this piece of code? Please keep in mind in code challenges like this I always try to code as concise as possible.

Examples in => output :

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

code:

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;
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$ – Mathieu Guindon Dec 11 '20 at 18:09
27
\$\begingroup\$

Name Classes properly.

What is a "Back Wards Prime"? I have no idea. I can guess what a Backward Prime is; perhaps you need to change the capitalization of the class!

I'm told that name is dictated by the coding challenge, so you can't change it for your challenge submission; but I'm leaving this comment stand -- the required class name is horrible.

Name variables properly.

This condition is confusing:

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

Is this really testing if the reversed value is different from the starting value? No! You're using the starting value as the loop variable, and continuously incrementing it with start++;. Make a new loop variable, and use a proper loop.

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

Reducing the work

You appear to have determined that any single digit prime, when read backwards, will not be different than the original, as well as 10 & 12 not being prime, and 11 not being different when reversed. Therefore, you need only consider values greater than 12. This optimization should be done before the loop starts, to avoid the overhead of testing the condition at each iteration.

You should also notice that 2 is the only even prime number, therefore you need not look at any even value. Instead of moving the start value up by 1, you could skip even values by incrementing by 2.

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

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

Avoid creating unnecessary intermediate results

Consider:

new StringBuilder(String.valueOf(start))

You are passing an integer to function which converts it into a string, and then returns that string. How does that function work? You then take that resulting string, and pass it to the constructor of the StringBuilder, to copy into the working area. Do you need that intermediate string?

new StringBuilder().append(candidate)

The StringBuilder.append(long) function takes a long value, and converts it into string characters directly inside the StringBuilder. This could potentially be faster. It is even 3 characters shorter, while using a longer variable name, so it is certainly more concise!

Also, consider sb.append(start + " ");. This converts start to a string (again), adds " " to it (internally using another StringBuilder!), and then appends this brand new string to sb. Instead, you could write:

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

No intermediate strings needs to be constructed and discarded.

Avoid useless work

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

If start is not prime, is there any point computing rev?

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

Better. But what about that candidate != rev? That looks like a very fast test, and isPrime(rev) is probably much, much slower.

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

But wait! How many times will candidate != rev be false? Very rarely? It may not gain anything, and the change may even slow the program down. Always profile!

Performance at the cost of conciseness

Constructing a new StringBuilder inside the loop can be a costly operation. You could construct one outside the loop, and use the .setLength(0) method to clear it, for the next iteration:

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

Major optimizations

Reduced search space

How many primes in the ranges 200-299, 400-699, and 800-899 will be reversible primes? How about in the ranges 2000-2999, 4000-6999, 8000-8999? How many in the ranges 20000-29999, 40000-69999, 80000-89999? And so on?

Zero. A reversible prime cannot start with a 2, 4, 5, 6, or 8, because when reversed, the number will be divisible by two or five, and thus won't be prime.

Implementing this observation in an efficient manner would certainly not make the code concise, but would dramatically speed it up. Left to student.

Sieve of Eratosthenes

You are potentially doing many, many primality checks using trial division. It may make more sense to use the Sieve of Eratosthenes to generate a BitSet of prime flags. Then isPrime(candidate) becomes a simple \$O(1)\$ lookup: prime.get(candidate).

Alternately, if maintaining a BitSet of \$10^{\lceil \log_{10}{end} \rceil}\$ bits is too memory intensive, use the sieve to generate the prime numbers up to \$\sqrt{10^{\lceil \log_{10}{end} \rceil}}\$, and use trial division with just those prime numbers, to avoid pointless trial division by odd composite numbers (9, 15, 21, 25, 27, 33, ...).

\$\endgroup\$
20
\$\begingroup\$
  • isPrime(9223372036854775783L) incorrectly returns false. Your i * i overflows, better use i <= n / i. Not sure it matters in the context of the problem, though. At least the reverse of this number isn't prime anyway. Division might be slower than multiplication, but might produce n % i as a by-product and a smart compiler might then use that instead of computing it again. So could also be faster overall.
  • isPrime(1) incorrectly returns true. Doesn't matter in this context, of course, as '1' is a palindrome and thus 1 doesn't count anyway.
  • Beware of reversed numbers overflowing: backwardsPrime(1999999999999999999L, 1999999999999999999L) crashes.
  • The line String.valueOf(... should be indented, to make clear it's a continuation of the previous line.
  • Testing start > 12 seems pointless and counterproductive. It certainly doesn't make the code more concise. I suspect it's intended as a performance optimization, but it only makes very few cases faster, plus they're very fast anyway, so it saves very little very rarely. But it costs extra for all other candidates. Not much, just very little, but for many. So overall it might waste more time than it saves.
  • You test isPrime(rev) before isPrime(start) and start != rev. Why? If you test isPrime(start) first and it fails, you don't even have to build rev (let alone test it).
  • If you do build rev anyway, it might be beneficial to do the three tests in order of increasing expected time. So start != rev first, as that's very fast. And then test primality of the smaller one of start and rev first. Testing start != rev also quickly rules out most cases ruled out by start > 12, so that's yet another reason to not additionally test start > 12.
  • Or test them both in parallel, otherwise you might spend a lot of time to determine that one is a large prime, only to then instantly see that the other one is an even number. Doh! Instead of testing divisors 2, 3, 4, ..., sqrt on one number and then again on the other, testing them in parallel tests the more likely divisors first. Let's say you tested divisors 2 to 96 on the first number already and you didn't test the second number yet. You could test the first number against 97, but that only has a ~1% chance to rule out the current candidate (pair) and go to the next one. Better test the other number against 2, which gives you a 50% chance. And that suboptimality didn't start at 97, it started at 3. So better try both numbers against 2, then both numbers against 3, etc. Until the square root of the smaller one. Then try divisors until the square root of the larger one only against the larger one.
  • Instead of building a String and then trimming that, it might be more efficient to remove a final space from the StringBuilder.

Then again, some of these will make the code longer, so go against your goal of being as concise as possible.

\$\endgroup\$
8
\$\begingroup\$

One optimisation that could be applied here: keep all the prime pairs that you discovered so far in HashSet. Lets take a look at example:

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

When we hit number 13, we discover that both 13 and 31 are prime -> save them in set;
When we hit 31 we look up this number in our set, and, because it is there, we can just skip this number.

Edit: Actually, we can go further and store numbers that we discovered as non-prime. In the example above: when we hit 19 (prime) we then check 91, which is not prime. Later on, when we hit 91, we already know that its not prime.

\$\endgroup\$
  • 4
    \$\begingroup\$ You could generalize this check simply by testing (with i being the current candidate in the loop) if (rev >= start && rev <= i) continue because we have exactly tested these numbers already. And rev <= i includes the test if the number is a palindrome \$\endgroup\$ – Falco Dec 7 '20 at 12:25
6
\$\begingroup\$
  • Iterating over some values in a certain range really asks for a for loop! Although the code is quite simple, it's even easier to understand when the variable referring to the current element is not called start. while (start <= end) is also a bit confusing. So I'd prefer for (long i=start ; i<=end ; i++).

  • I would also introduce a function rev() to be able to refer to the reverse of i just by rev(i). This way you can also move the rather clunky expression involving the StringBuilder out of the main method.

     public static Long rev(Long n) {
         StringBuilder b = new StringBuilder(String.valueOf(n));
         return Long.parseLong(b.reverse().toString());
     }
    
  • Finally, the optimizations in isPrime are making the code harder to understand and a bit confusing (shouldn't isPrime(2) return true?). I would only use the square root optimization i * i <= n since it improves efficiency a lot without adding much noise.

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

Given these two helpers you can reduce the main method to this rather minimal version:

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();
}
\$\endgroup\$
1
\$\begingroup\$

You have skipped checking for divisibility by even numbers. You only need to check for divisibility by prime numbers. Aside from 2 and 3, every prime leaves remainder 1 or 5 on division by 6. (Proof: 0, 2, 3, 4 share a common factor of 2 or 3 with 6.) As a consequence, you can step alternately by 2 and 4. From

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

Just check the 6k+1 and 6k+5 cases, eliminating about a third of the comparisons. Also, stop recomputing the termination condition for the loop. This can be replaced with comparison with a constant. See https://stackoverflow.com/questions/15212533/java-square-root-integer-operations-without-casting for a discussion of Java integer square root.

static boolean isPrime(long n) {
    if( (n % 2 == 0) || (n % 3 == 0) ) return false;
    int i = 5;
    ubound = (int) Math.sqrt(n);  
    while( i <= ubound )  {
        if( (n % i == 0) || (n % (i + 2) == 0) )
            return false;
        i += 6;
    }
    return true;
}

This reduction of cases can be extended. After 2, 3, and 5, every prime leaves remainder 1, 7, 11, 13, 17, 19, 23, or 29 modulo 30. (All other numbers have a common factor with 30.) This reduces the number of modular reductions by 4/5. Although one can keep going, there is seldom any benefit. (For instance, there are 48 remainders to check modulo 2 * 3 * 5 * 7, meaning we have only eliminated 1/7 of iterations of the modulo 30 version.)

If you have a good integer GCD implementation, you can replace these modular checks with a single GCD. One should profile to find out where the crossover from multiple modular reduction-comparisons is outperformed by a single GCD calculation. Here's a version that is probably not at all faster because the gains don't come until we work with a much larger modulus and its list of candidate primes.

static boolean isPrime(long n) {
    long modulus = 2*3*5*7*11*13*17*19*23*29; // An excellent place for C++'s static const.
    // modulus^2 > Long.MAX_VALUE
    if( n == 1 ) return false;
    if( (n==2) || (n==3) || (n==5) || (n==7) || (n==11) ||  (n==13) ||  (n==17) ||  (n==19) || (n==23) ||  (n==29) ) return true;
    if(gcd(modulus, n) > 1) return false;
    for(int i = 31; i <= n/i  ; i += 6) {
        if( ( (gcd(modulus, i) == 1) && (n % i == 0) ) 
         || ( (gcd(modulus, i+4) == 1) && (n % (i+4) == 0) ) )
            return false;
    }
    return true;
}

static long gcd(long a, long b) {
    if ( b == 0 ) return a;
    return gcd(b, a % b);
}

I've measured the GCD version to eventually outperform table-based (list, array, association) methods for holding the list of guaranteed-composite remainders. I have never seen the GCD-based version outperform the hand unrolled version. You would like to adjust the modulus based on the intended magnitudes of ns, but that puts you in the slow, table-based modular reductions. So either have a fixed table of reductions or use the GCD method and accept that it is a bit slow for small ns.

\$\endgroup\$
  • \$\begingroup\$ I tried that last code, didn't compile. Had to make gcd static and change its int to long. And then isPrime(13) claimed false. Also, what's the point of checking gcd(modulus, i) == 1? It seems to be an attempt to avoid checking n % i == 0 when that's pointless due to i being composite, but I'd say that that gcd-check costs way more time than it saves. Surely n % i == 0 is much faster? \$\endgroup\$ – superb rain Dec 8 '20 at 16:32
  • \$\begingroup\$ @superbrain : gcd was copied from cited source withotu change. My code had an omission (stopped typing primes into modulus before done). It was fixed before your comment, but I suspect you copied the code in the interim. This would make the code not treat 13 as prime. We check gcd(modulus, i) = 1 to only test for divisibility by likely primes. As I said in the text, I've only seen the gcd code beat structure-based modular checks, but the problem is not the log-time gcds. \$\endgroup\$ – Eric Towers Dec 8 '20 at 16:38
  • \$\begingroup\$ No, I actually came here because/after you bumped the question with your edit :-). So the current version claims 13 isn't prime, and also those other small primes. I just picked 13 because that's the first that's relevant for the OP's use case. Hmm, if the log-time gcds aren't "the problem", then what is? Not sure what you mean with that. \$\endgroup\$ – superb rain Dec 8 '20 at 16:43
  • \$\begingroup\$ @superbrain : Fixed that (missed a line in cut-and-paste). Trying to determine why my code didn't do what you described also detected an error in OP's code: 1 is not prime. "The problem" is the runtime, precisely as explained in the text: hand unrolled modular checking always beats GCD eventually beats data structure modular checking. Notice that in the particular case shown, there are > 10^9 remainders to check in the unrolled loop (i.e., there are just over 10^9 numbers up to modulus that are relatively prime to modulus). \$\endgroup\$ – Eric Towers Dec 8 '20 at 16:57
  • \$\begingroup\$ Yeah, the OP's failure at 1 is the second item in my own answer. I didn't mention that it also fails negative numbers because I figured everyone would fix it by checking n <= 1, but I guess you proved me wrong :-P. Your updated version still doesn't compile. And after adding the missing ||, it claims that most numbers under 100 are prime, including 4 and 6. With hand-unrolled, do you mean a big amount of lines like || (n % (i+...) == 0), one for each hole in the wheel? That looks somewhat reasonable. I still don't think your gcd version shown here makes sense. \$\endgroup\$ – superb rain Dec 8 '20 at 17:32
0
\$\begingroup\$

Reversing with string operations will be relatively slow. Try something like:

public static long reverse(long x) {
    long reverseX = 0;
    while (x > 0) {
        reverseX *= 10;
        reverseX += x % 10;
        x /= 10;
    }
    return reverseX;
}
\$\endgroup\$
  • \$\begingroup\$ How much faster is this? \$\endgroup\$ – superb rain Dec 9 '20 at 13:41
  • \$\begingroup\$ I haven't measured, but think of all the work that Long.parseLong(new StringBuilder(String.valueOf(start)).reverse().toString()) - creating and destroying objects, writing, reversing, and parsing strings. I'm pretty confident the above will be a lot faster :) \$\endgroup\$ – Paul Crowley Dec 9 '20 at 15:43
  • \$\begingroup\$ How does this code handle numbers that are too long for long when reversed? That's obviously a problem with the original code, too, of course... \$\endgroup\$ – Toby Speight Jan 1 at 16:08
  • \$\begingroup\$ I think it will do OK, but for bigints I'd use the fact that you're reversing lots of integers contrained in a particular short range to come up with a more efficient algorithm. \$\endgroup\$ – Paul Crowley Jan 1 at 20:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.