I've been a zone leader with DZone since 2008, and I'm crazy about community. Every day I get to work with the best that JavaScript, HTML5, Android and iOS has to offer, creating apps that truly make at difference, as principal front-end architect at Avego. James is a DZone Zone Leader and has posted 639 posts at DZone. You can read more from them at their website. View Full User Profile

Thursday Code Puzzler: Finding Twin Primes

04.26.2012
| 3934 views |
  • submit to reddit

Time for our weekly code puzzle. The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you think is suitable. Today problem is to find all the twin primes within a certain range. A twin prime is a pair of prime numbers that differs by two. Two examples would be (3,5) and (5,7).  

What you have to do is write a method/function that takes an integer input (let's call it limit) and finds all the twin primes up to that limit.

As you are free to use any language, it will be interesting to see which approach will give the most readable code.

Note: Even though there really is nothing stopping you from finding a solution to this on the internet, try to keep honest, and come up with your own answer.  It's all about the participation!

Thanks to everyone who participated in the last few code puzzlers. 

Comments

Shruti Gangras replied on Thu, 2012/04/26 - 5:31am

 

will try to find a more optimized version 

public void testTwinPrime() {
        Date startDate;
        Date endDate;

        startDate = new Date();
        printTwinPrimesForRange(1, 10_000);
        endDate = new Date();
        System.out.println(endDate.getTime() - startDate.getTime()+" milliseconds");
    }

    private void printTwinPrimesForRange(int start, int end) {
        boolean toggle = false;
        boolean isPrime = false;
        int toTest;
        int j;
        int pair = 0;

        for (toTest = start; toTest <= end; toTest++) {
            for (j = 2; j <= toTest/2+1; j++) {
                if (toTest % j == 0) {
                    isPrime = false;
                    break;
                } else {
                    isPrime = true;
                }
            }
            if (isPrime) {
                toggle = !toggle;
                if (toggle) {
                    pair = toTest;
                } else {
                    System.out.println("pair is (" + pair + "," + toTest + ")");
                }
            }

        }
    }

 

Vorname Nachname replied on Thu, 2012/04/26 - 3:51pm

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

Andrea Del Bene replied on Thu, 2012/04/26 - 10:25am

In "dirty" JavaScript :)

function isPrime(number){
	var sqrtValue = Math.sqrt(number);
	
	for(var i = 2;i <= sqrtValue; i++){
		if(number % i === 0)
			return false;
	}
	
	return true
}

function twinPrimeRange(from, to){
	var lastPrimeFound;
	
	for(var i = from;i <= to; i++){
		if(i % 2 !== 0){
			if(isPrime(i)){
				if(i - 2 === lastPrimeFound)
					alert("Twin found! " + lastPrimeFound + ", " + i);
				lastPrimeFound = i;
			}
		}			
	}
	
}

 

 

 

Mike P(Okidoky) replied on Fri, 2012/04/27 - 2:23pm

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.

Evgenij Kozhevnikov replied on Fri, 2012/04/27 - 9:52am

Scala:

object Main extends App{

  def primes(listOfNaturals: List[Int]) = {
    require(!listOfNaturals.contains(0))
    require(!listOfNaturals.exists(_ < 0))

    listOfNaturals.filter((x: Int) => {
      x > 1 && (2 to x - 1).find(p => x % p == 0) == None
    })
  }

  def twins(listOfPrimes: List[Int]): Map[Int, Int] = {
    var result = Map[Int, Int]()
    for (prime <- listOfPrimes) {
      val soPrime = listOfPrimes.find(_ - prime  == 2)
      if (soPrime != None) {
        result += (prime -> soPrime.get)
      }
    }
    result
  }

  def twinPrimes(high: Int) = {
    twins(primes((1 to high).toList))
  }

  println(twinPrimes(100))

}

Daniel Siwiec replied on Fri, 2012/04/27 - 10:52pm in response to: Shruti Gangras

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.

Daniel Siwiec replied on Fri, 2012/04/27 - 11:18pm

How about this?

public class TwinPrimes {

	public static void main(String[] args) {
		long start = System.currentTimeMillis();
		int limit = 10000;
		findTwinPrimes(limit);
		long end = System.currentTimeMillis();
		System.out.println("It took: " + (end - start) + " ms");
	}

	private static void findTwinPrimes(int limit) {

		for (int current = 3; current < limit - 2; current += 2) {
			if (isPrime(current)) {
				if (isPrime(current + 2)) {
					System.out.println("Twin primes: " + current + ", "	+ (current + 2));
				}
			}
		}
	}

	private static boolean isPrime(int candidate) {
		for (int i = 2; i < candidate / 2 + 1; i++) {
			if (candidate % i == 0) {
				return false;
			}
		}
		return true;
	}

}

 

Evgenij Kozhevnikov replied on Sat, 2012/04/28 - 1:26am in response to: Daniel Siwiec

Cool sources)

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.