Programming Praxis

7 Responses to “Twin Primes”

1. ardnew said

   April 17, 2012 at 10:17 PM

   Perl solution, lots of code

   use strict;
   use warnings;
   
   our $BITS = 32;
   
   # checks if the bit representing parameter n is set
   sub get($$)
   {
     my ($p, $n) = @_;  
     return 0 unless $n & 1;
     return 1 if $n == 2;
     $n >>= 1; # every bit represents an odd integer  
     return $$p[int($n / $BITS)] >> $n % $BITS & 1;
   }
   
   # sets the bit representing parameter n to b
   sub set($$$)
   {
     my ($p, $n, $b) = @_;  
     return unless $n & 1;
     $n >>= 1; # every bit represents an odd integer  
     my ($i, $o) = (int($n / $BITS), $n % $BITS);
     $$p[$i] &= ~(1 << $o);
     $$p[$i] |= !!$b << $o;
   }
   
   # computes the modular inverse
   sub mod_inverse($$) 
   { 
     my $m;
     my ($a, $b, $x, $y, $n) = ((shift) % ($m = shift), $m, 1, 0);
     
     while (0 != $a) 
     { 
       $n = int($b / $a);
       ($a, $b, $x, $y) = ($b - $n * $a, $a, $y - $n * $x, $x); 
     } 
     return $y % $m; 
   } 
   
   #
   # Our primes/sieve table is represented by a list P[] of
   # 32-bit integers. 
   # 
   # We map each natural number K to the bit table P[][] using:
   #
   #     K := 0, K is even
   #     K := P[ K / 64 ][ K (mod 64) ], K is odd
   #
   # This mapping has the advantage of only needing to keep
   # a record of the odd integers, reducing required memory.
   #
   # The list returned is the midpoints of the twins
   #
   sub sieve($)
   {
     my ($n, @a, @b) = shift;  
     
     my $m = sqrt $n;
     my @pairs = (4);
     
     # initialize the bit tables
     (push @a, 0), (push @b, 0) 
       foreach (0 .. ($n >> 1) / $BITS);
     
     # set all our numbers of the form 6k +/- 1
     map { set(\@a, 6 * $_ - 1, 1) } 1 .. ($n + 1) / 6;
     map { set(\@b, 6 * $_ + 1, 1) } 1 .. ($n - 1) / 6;
     
     # perform the sieve
     for (my $i = 3; $i < $m; $i += 2)
     {
       my ($r, $s) = (mod_inverse( 6, $i), 
                      mod_inverse(-6, $i));
                      
       set(\@a, $r, 0) unless get(\@a, $r);
       set(\@b, $s, 0) unless get(\@b, $s);
       
       my $k = $i + $i;
       
       set(\@a, $k, 0), set(\@b, $k, 0), $k += $i 
         while $k < $n;
     }
     
     # align the bits for easy matching
     $_ <<= 1 foreach @a;
     
     # if bits are set in corresponding positions,
     # add the midpoint to our list
     get(\@a, $_) and get(\@b, $_) and 
       push @pairs, $_ - 1 foreach 1 .. $n;
   
     return @pairs;  
   }
   
   0+@ARGV and print join ' ', sieve($ARGV[0]) or 
     die "\nusage:\n\t$0 <upper limit>\n\n";
   
2. mrjbq7 said

   April 19, 2012 at 10:03 PM

   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
3. sibendu dey said

   April 27, 2012 at 4:55 PM

   #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);
   }
   }
   }
   }
4. Dreddy said

   May 1, 2012 at 1:45 AM

   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]);
   }
   }
5. ardnew said

   May 2, 2012 at 4:35 PM

   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..
6. Benjamin Samson said

   May 14, 2012 at 2:51 AM

   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

7. Benjamin Samson said

   May 14, 2012 at 2:53 AM

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