3
\$\begingroup\$

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

  1. I'm overdoing it/the plain way would be faster.
  2. 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<Integer> getPrimesUnder(int limit) {
        int prime;
        List<Integer> primes = new ArrayList<>();
        List<Integer> numbers = new ArrayList<>();

        for (int i = 2; i < limit; i++) {
            numbers.add(i);
        }

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

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

        return primes;
    }

    private static int computeLargestPrimePalindrome(int limit) {
        List<Integer> 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
    }
}
\$\endgroup\$
6
\$\begingroup\$

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<Integer> 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;
}
\$\endgroup\$
4
\$\begingroup\$

A 3-digit number n is palindromic iff n % 10 == n / 100, so no string manipulations are called for. Same technique also works for arbitrary numbers, as long as you know how many digits there are.

To test a string, there is no need to reverse and compare strings:

    for (int i = 0, j = s.length() - 1; i < j; ++i, --j) {
        if (s.charAt(i) != s.charAt(j))
            return false;
    }
    return true;
\$\endgroup\$

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.