Premium palindromic primes

Challenge: Write a program which determines the largest prime palindrome less than 1000.

The answer is 929, and my program correctly finds and prints this, but actually ended up being more complex than I expected.

I'd like a general review, but also want to pinpoint if

• I'm overdoing it/the plain way would be faster.

• I'm doing anything inefficiently/there are superior alternatives.

Solution

import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;

public class PrimePalindrome {
    public static void main(String[] args) {
        final int LIMIT = 1000;

        System.out.println(computeLargestPrimePalindrome(LIMIT));   
    }

    private static boolean isPalindromic(int s) {
        return s == reverse(s);
    }

    private static int reverse(int n) {
        return Integer.parseInt(
            new StringBuilder(Integer.toString(n)).reverse().toString()
        );
    }

    /* Finding all prime numbers under an integer,
    using Sieve of Eratosthenes
    http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes */
    private static List getPrimesUnder(int limit) {
        int prime;
        List primes = new ArrayList<>();
        List numbers = new ArrayList<>();

        for (int i = 2; i  primes = getPrimesUnder(limit);
        ListIterator li = primes.listIterator(primes.size());

        while (li.hasPrevious()) {
            if (isPalindromic((int) li.previous())) {
                return (int) li.next();
            }
        }

        return -1; // if none are found
    }
}

This is generally nicely presented code, and it is good to read.

Your suspicions that the code is not as efficient as it could be, is correct. There's some simple things to fix, and some harder ones. First though, the sieve:
Sieve

A sieve of Eratosthenes is best implemented as an actual array. Your code uses a list as a type of queue. Let's look at this code here:

while (!numbers.isEmpty()) {
        prime = numbers.get(0);
        primes.add(prime);

        for (int i = prime; i < limit; i += prime) {
            numbers.remove((Integer) (i));
        }
    }

That code takes the first number in the un-processed ones, and removes it, it's prime. That's fine, no problem, but.... Look at what numbers is:

List numbers = new ArrayList<>();

It's an array list, so what the first loop through here does:

for (int i = prime; i < limit; i += prime) {
            numbers.remove((Integer) (i));
        }

is essentially remove the item at position 0, which, for an array list, means every other item needs to be shuffled forward one spot. To remove the first item, you have also moved every other item.

Again, when you find the next multiples of the prime, you are shifting each larger value by 1 position as well.

This could result in a lot of shuffling..... a huge amount, in fact.

What's worse, though, is as you go through the multiples of the prime (for example, 7), you say:

remove(7);
remove(14);
....
remove(987); // (141 * 7)

When you say remove (987) you have to scan the entire list looking for that value.... so you scan all the early values, and shift all the later values.

The Sieve is traditionally implemented as a fixed, primitive array, of booleans:

boolean[] sieve = new boolean[1000];
Arrays.fill(sieve, true);

The above code initializes 1000 boolean members, and sets them all to true.

Now, with your sieve like that, you can simply:

for (int prime = 2; prime < sieve.length; prime++) {
    if (sieve[prime]) {
        // this is a prime number
        for (int notPrime = prime * 2; np < sieve.length; notPrime += prime) {
            sieve[notPrime] = false;
        }
    }
}

Now, you have removed all non-prime values by setting the index value to be false.

There are ways to make that faster, but, the important thing is there's no scanning for values, or shifting things either.
Reverse

Your reverse method converts things to a string, and reverses that. I would prefer an int-based system:

private static int reverse(int p) {
    int reverse = 0
    while (p != 0) {
        reverse *= 10;
        reverse += (p % 10);
        p /= 10;
    }
    return reverse;
}

StackExchange Code Review Q#79705, answer score: 6