## Twin Primes

### April 17, 2012

Our function to compute the twin primes less than *n* is a straight forward rendering of the algorithm given above, except that there is no need for two bitarrays; as long as we keep the indices straight, the two bitarrays can be combined into one, reducing the space requirement by half. The bitarray and sieving primes are initialized first. The outer `do`

runs through the sieving primes; the first inner `do`

, on *i*, sifts primes of the form 6*k*−1, and the second inner `do`

, on *j*, sifts primes of the form 6*k*+1. Finally, the named `let`

sweeps up the twin primes, reporting their average 6*k*, including the initial 4 that isn’t computed because it’s not of the form 6*k*±1.

`(define (twins n)`

(let* ((len (quotient n 6))

(bits (make-vector len #t))

(ps (cddr (primes (inexact->exact (ceiling (sqrt n)))))))

(do ((ps ps (cdr ps))) ((null? ps))

(let* ((x (inverse 6 (car ps)))

(x (+ x (if (= (car ps) (- (* 6 x) 1)) (car ps) 0))))

(do ((i (- x 1) (+ i (car ps)))) ((<= len i))

(vector-set! bits i #f)))

(let* ((x (inverse -6 (car ps)))

(x (+ x (if (= (car ps) (+ (* 6 x) 1)) (car ps) 0))))

(do ((j (- x 1) (+ j (car ps)))) ((<= len j))

(vector-set! bits j #f))))

(let loop ((t 0) (ts (list 4)))

(cond ((= len t) (reverse ts))

((vector-ref bits t)

(loop (+ t 1) (cons (* 6 (+ t 1)) ts)))

(else (loop (+ t 1) ts))))))

We use `inverse`

and `primes`

from two previous exercises. You can run the program at http://programmingpraxis.codepad.org/68zEdHFA.

Pages: 1 2

Perl solution, lots of code

Solved using Factor.

: twin-primes-upto ( n — seq )

primes-upto 2 <clumps> [ first2 – 2 = not ] filter ;

http://re-factor.blogspot.com/2012/04/twin-primes.html

#include

#include

int primecheck(int);

void twinprime(int);

void main() {

int number;

clrscr();

printf(“Enter the MAximum number\n”);

scanf(“%d”,&number);

twinprime(number);

printf(“\nThank You!!”);

getch();

}

int primecheck(int prime) {

int i,flag=1;

for(i=2;i<=(prime/2);i++) {

if(prime%i==0) {

flag=0;

return flag;

}

}

return flag;

}

void twinprime(int max) {

int i,j;

for(i=2;i<=(max-2);i++) {

if(primecheck(i)==1) {

if(primecheck(i+2)==1) {

printf("Twin primes are :%d %d\n",i,i+2);

}

}

}

}

Sorry, at work, so syntax might be appalling but off the top of my head I thought something like this idea work:

(warning may contain java-ish-ness)

int[] primeArray;

//find the primes less than N and by checking the usual does it divide by anything except 1 and itself, then add these to an array

for(int i = 3; i < n; i++){

int countOfDivisions = 0;

for(t = 2; t < i – 1; t++){

if((i.toNum() % t.toNum()) == 0){ //convert to something with decimals and mod that bad boy

countOfDivisions++;

}

}

if(countOfDivs == 0)

int.push(i); //add, push, attach, whatever

}

//cycle through the array of primes found and print out the pairs, length – 2 to stay in array but check the position after i

for(int i = 0; i < primeArray.length – 2; i++){

if(primeArray[i + 1] – primeArray[i] == 2){

System.out.println(primeArray[i] + ", " + primeArray[i + 1]);

}

}

I don’t mean to be a prude, but all other solutions posted on here completely disregard the proposed algorithm in the exercise description. Instead, they are either filtering the standard prime sieve, or repeatedly doing trial division. Both of these methods are kinda missing the point..

Here’s my solution in Python:

def twinPrimes(n):

#list odd numbers

odd = []

a = 3

while a <= n:

odd.append(a)

a = a + 2

#list prime numbers via sieve of eratosthenes

for p in odd:

q = 2*p

while p <= odd[-1]:

p = p + q

if p in odd:

odd.remove(p)

`#odd now contains all prime numbers less than or equal to n`

for i in odd:

if i + 2 in odd:

print i, i + 2

Guys, can somebody tell me how to properly insert code here. Thanks! :)