Thursday Code Puzzler: Finding Twin Primes

The following code produced 8169 results for a limit of 1000000 in 390 msecs.

    public List<Integer> findTwinPrimes(int limit) {
        List<Integer> primeNumbers = new ArrayList<Integer>(1000000);
        List<Integer> result = new ArrayList<Integer>(10000);
        primeNumbers.add(2);

        int lastPrime = 2;
        
        if (limit == 2)
            return result;
        
        int sqrt = (int) Math.sqrt(limit);

        for (int i = 3; i <= limit; i++) {
            boolean isPrime = true;
            for (Integer prime : primeNumbers) {
                if (prime > sqrt) {
                    break;
                }

                if (i % prime == 0) {
                    isPrime = false;
                    break;
                }
            }
            
            if (isPrime) {
                primeNumbers.add(i);
                if (lastPrime + 2 == i) {
                    result.add(lastPrime);
                }
                
                lastPrime = i;
            }
        }
        
        return result;
    }

I solemnly swear I did not peek at any existing algorithms.

I focused on performance. It might well be that the only way to make this faster is by using assembler - which is very doable, because the code is very simple. I doubt if a C/C++ version would run any faster. I purposely run the algorithm 5 times to give the JVM the chance to compile to machine code and eliminate JVM warm up.

The code is hardwired in main() with the limit set to 1 million, but you can change it to whatever. I haven't timed it but it seems pretty instant. I'd love to write an assembler (Intel) version of it, but don't have the time. I'm avoiding divisions here. Instead of finding primes, I create an array and run a dual nested loop listing all the non-primes and marked them in the array. Whatever was left untouched is a prime. It then can iterate the array, and look for primes and primes two steps away. The resolution of the array is half, because every other number can not be a prime. I've also figured out how to avoid having to do multiplications inside the inner loop. I had tricks that I remembered when writing low level graphics code from 20 years ago, Bresenhem type stuff...

public class TwinPrimes
{
	public static void main(String[] args)
	{
		for (int i = 0; i < 5; i++)
		{
//			long time = twinPrimes(100 * 1000* 1000);
			long time = twinPrimes(1* 1000* 1000);
//			long time = twinPrimes(100);
			System.out.println(time + " ms\n");
		}
	}
	
	public static long twinPrimes(int max)
	{
		long time = System.currentTimeMillis();
		boolean _nonPrimes[] = new boolean[max / 2];
		for (int i = 3; ; i += 2)
		{
			int j = i * i;
			if (j >= max)
				break;
			for (; j < max; j += i)
			{
				if ((j & 1) != 0)
					_nonPrimes[j / 2] = true;
			}
		}
		time = System.currentTimeMillis() - time;
		int report = 25;
		for (int n = 2; n < _nonPrimes.length; n++)
		{
			if (!_nonPrimes[n] && !_nonPrimes[n - 1])
			{
				if (--report == 0)
				{
					System.out.println("more...");
					break;
				}
				int a = (n - 1) * 2 + 1, b = n * 2 + 1;
				System.out.println(a + ", " + b);
			}
		}
		return time;
	}
}

Update: fixed to allow for higher limit and major efficiency improvement.
It can find all the pairs at a limit of 100,000,000 in about 3 seconds !
1,000,000 in about 5 ms.
Non-cluttery code should be easy to read, even by new-comers, coops, people used to other languages.

That doesn't seem to work. It's supposed to find prime numbers that differ by two, but instead it's returning pairs of two consecutive prime numbers.

Cool sources)