[Solved] Printing n pairs of prime numbers, C++

Question

Here is the top-level simple pseudo-code for such a beast:

def printTwinPrimes(count):
    currNum = 3
    while count > 0:
        if isPrime(currNum) and isPrime(currNum + 2):
            print currnum, currnum + 2
            count = count - 1
        currNum = currNum + 2

It simply starts at 3 (since we know 2,4 is impossible as a twin-prime pair because 4 is composite). For each possibility, it checks whether it constitutes a twin-prime pair and prints it if so.

So all you need to do (other than translating that into real code) is to create isPrime(), for which there are countless examples on the net.

For completeness, here’s a simple one, by no means the most efficient but adequate for beginners:

def isPrime(num):
    if num < 2:
        return false
    root = 2
    while root * root <= num:
        if num % root == 0:
            return false
        root = root + 1
    return true

Though you could make that more efficient by using the fact that all primes other than two or three are of the form 6n±1, n >= 1^(a):

def isPrime(num):
    if num < 2: return false
    if num == 2 or num == 3: return true
    if num % 2 == 0 or num % 3 == 0: return false
    if num % 6 is neither 1 nor 5: return false

    root = 5
    adder = 2                   # initial adder 2, 5 -> 7
    while root * root <= num:
        if num % root == 0:
            return false
        root = root + adder     # checks 5, 7, 11, 13, 17, 19, ...
        adder = 6 - adder       # because alternate 2, 4 to give 6n±1
    return true

In fact, you can use this divisibility trick to see if an arbitraily large number stored as a string is likely to be a prime. You just have to check if the number below it or above it is divisible by six. If not, the number is definitely not a prime. If so, more (slower) checks will be needed to fully ascertain primality.

A number is divisible by six only if it is divisible by both two and three. It’s easy to tell the former, even numbers end with an even digit.

But it’s also reasonably easy to tell if it’s divisible by three since, in that case, the sum of the individual digits will also be divisible by three. For example, lets’ use 31415926535902718281828459.

The sum of all those digits is 118. How do we tell if that’s a multiple of three? Why, using exactly the same trick recursively:

118: 1 + 1 + 8 = 10
 10: 1 + 0     = 1

Once you’re down to a single digit, it’ll be 0, 3, 6, or 9 if the original number was a multiple of three. Any other digit means it wasn’t (such as in this case).

^(a) If you divide any non-negative number by six and the remainder is 0, 2 or 4, then it’s even and therefore non-prime (2 is the exception case here):

6n + 0 = 2(3n + 0), an even number.
6n + 2 = 2(3n + 1), an even number.
6n + 4 = 2(3n + 2), an even number.

If the remainder is 3, then it is divisible by 3 and therefore non-prime (3 is the exception case here):

6n + 3 = 3(2n + 1), a multiple of three.

That leaves just the remainders 1 and 5, and those numbers are all of that form 6n±1.

Accepted Answer