Source: Saari Development: Ruby: One liner to strip the line number from code posted [blogspot.com]

   1  
   2  ruby -lne 'puts $_.gsub(/^\s+?\d+\s/,"")' ali.rb > ali.rb

Here's a page that allows you to strip line numbers without any script [rorbuilder.info] or here http://rubyurl.com/umxP .

// description of your code here
I present with this Ruby code a new class of Number Theory Sieves (NTS)
to generate primes numbers upto some number N, which I believe now
represent the fastest way to generate prime numbers. The general number
theory can utilize a class of prime generator functions, which have the
same form, and which can be implemented in the same manner. These NTS
can be inherently implemented in parallel with multiple processors.

The classical brute-force method to generate primes upto some N is the
Sieve of Eratothenes (SoE). In 2002/3 Atkin & Bernstein proposed what has
become known as the Sieve of Atkin (SoA), which was known to be the fastest
method to generate primes. My general number theory based Sieve of Zakiya (SoZ)
represents a multiple times increase in performance over the SoA, while being
easier to understand, code, and extend with newer prime generator functions.

I also used the number theory to created a primality tester, whose code
is short and elegant, which I also believe is the fastest method to test
for primality while being deterministic. Thus, it should replace other
non-deterministic or probabilistic methods, such as Miller-Rabin, et al.

I started this work this first week in May 2008, and present this code
herein on Friday, June 6, 2008.

The development of this work is presented in the paper:
"Ultimate Prime Sieve -- Sieve of Zakiya"
the pdf can be download from here:

http://www.4shared.com/dir/7467736/97bd7b71/sharing.html

   1  
   2  #!/usr/local/bin/ruby -w
   3  
   4  require 'benchmark' 
   5  
   6  class Integer
   7  
   8     def primes1
   9        # classical brute-force Sieve of Eratosthenes (SoE)
  10        # initialze sieve array with all integers starting at i=2
  11  
  12        sieve = [nil, nil].concat((2..self).to_a)
  13  
  14        (2 .. Math.sqrt(self).to_i).each do |i|
  15  
  16           next unless sieve[i]
  17           (i*i).step(self, i) { |j| sieve[j] = nil }
  18        end
  19        sieve.compact!
  20     end  
  21  
  22     def primes2
  23        # classical brute-force Sieve of Eratosthenes (SoE)
  24        # initialize sieve array with odd integers for odd indexes, then 2
  25  
  26        sieve = [];  3.step(self, 2) { |i| sieve[i] = i };  sieve[2] = 2
  27  
  28        3.step(Math.sqrt(self).to_i, 2) do |i| 
  29           next unless sieve[i]
  30           (i*i).step(self, i<<1) { |j| sieve[j] = nil }
  31        end
  32        sieve.compact!
  33     end 
  34  
  35     def primes3
  36        # http://everything2.com/index.pl?node_id=1176369
  37        # all prime candidates > 3 are of form  6*k+1 and 6*k+5
  38        # initialize sieve array with only these candidate values
  39        n1, n2 = 1, 5;  sieve = [] 
  40        while n2 < self
  41           n1 += 6;   n2 += 6;   sieve[n1] = n1;   sieve[n2] = n2
  42        end
  43        # now initialize sieve array with first 3 primes, resize array
  44        sieve[2]=2;  sieve[3]=3;  sieve[5]=5;  sieve=sieve[0..self]
  45  
  46        5.step(Math.sqrt(self).to_i, 2) do |i| 
  47           next unless sieve[i]
  48           (i*i).step(self, i<<1) {|j| sieve[j] = nil }
  49        end   	
  50        sieve.compact!
  51     end
  52  
  53     def primesP3
  54        # all prime candidates > 3 are of form  6*k+1 and 6*k+5
  55        # initialize sieve array with only these candidate values
  56        n1, n2 = 1, 5;  sieve = [] 
  57        while n2 < self
  58           n1 += 6;   n2 += 6;   sieve[n1] = n1;  sieve[n2] = n2
  59        end
  60        # now initialize sieve array with primes < 6, resize array
  61        sieve[2]=2;  sieve[3]=3;  sieve[5]=5;  sieve=sieve[0..self]
  62  
  63        5.step(Math.sqrt(self).to_i, 2) do |i| 
  64           next unless sieve[i]
  65  	 #  p5= 5*i, k = 6*i,  p7 = 7*i  
  66  	 p1 = 5*i;  k = p1+i;  p2 = k+i
  67  	 while p1 <= self
  68  	     sieve[p1] = nil;  sieve[p2] = nil;  p1 += k;  p2 += k
  69  	 end    
  70        end   	
  71        sieve.compact!
  72     end
  73  
  74  
  75     def primesP3a
  76        # all prime candidates > 3 are of form  6*k+1 and 6*k+5
  77        # initialize sieve array with only these candidate values
  78        # where sieve contains the odd integers representatives
  79        # convert integers to array indices/vals by  i = (n-3)>>1 = (n>>1)-1
  80        n1, n2 = -1, 1;  lndx= (self-1) >>1;  sieve = []
  81        while n2 < lndx
  82           n1 +=3;   n2 += 3;   sieve[n1] = n1;  sieve[n2] = n2
  83        end
  84        #now initialize sieve array with (odd) primes < 6, resize array
  85        sieve[0] =0;  sieve[1]=1;  sieve=sieve[0..lndx-1]
  86  
  87        5.step(Math.sqrt(self).to_i, 2) do |i|
  88           next unless sieve[(i>>1) - 1]
  89  	 # p5= 5*i,  k = 6*i,  p7 = 7*i  
  90  	 # p1 = (5*i-3)>>1;  p2 = (7*i-3)>>1;  k = (6*i)>>1
  91  	 i6 = 6*i;  p1 = (i6-i-3)>>1;  p2 = (i6+i-3)>>1;  k = i6>>1
  92  	 while p1 < lndx
  93  	     sieve[p1] = nil;  sieve[p2] = nil;  p1 += k;  p2 += k
  94  	 end    
  95        end
  96        return [2] if self < 3
  97        [2]+([nil]+sieve).compact!.map {|i| (i<<1) +3 }
  98     end
  99  
 100     def primesP5
 101        # all prime candidates > 5 are of form  30*k+(1,7,11,13,17,19,23,29)
 102        # initialize sieve array with only these candidate values
 103        n1, n2, n3, n4, n5, n6, n7, n8 = 1, 7, 11, 13, 17, 19, 23, 29;  sieve = [] 
 104        while n8 < self
 105           n1 +=30;   n2 += 30;   n3 += 30;   n4 += 30
 106  	 n5 +=30;   n6 += 30;   n7 += 30;   n8 += 30
 107  	 sieve[n1] = n1;  sieve[n2] = n2;  sieve[n3] = n3;  sieve[n4] = n4
 108  	 sieve[n5] = n5;  sieve[n6] = n6;  sieve[n7] = n7;  sieve[n8] = n8
 109        end
 110        # now initialize sieve with the primes < 30, resize array
 111        sieve[2]=2;  sieve[3]=3;  sieve[5]=5;  sieve[7]=7;  sieve[11]=11;  sieve[13]=13
 112        sieve[17]=17; sieve[19]=19;  sieve[23]=23;  sieve[29]=29;   sieve=sieve[0..self]
 113  
 114        7.step(Math.sqrt(self).to_i, 2) do |i| 
 115           next unless sieve[i]
 116  	 # p1=7*i, p2=11*i, p3=13*i ---- p6=23*i, p7=29*i, p8=31*i,  k=30*i
 117  	 n6 = 6*i;  p1 = i+n6;  p2 = n6+n6-i;  p3 = p1+n6;  p4 = p2+n6
 118  	 p5 = p3+n6;  p6 = p4+n6;  p7 = p6+n6;  k = p7+i;  p8 = k+i
 119  	 while p1 <= self
 120  	     sieve[p1] = nil;  sieve[p2] = nil;  sieve[p3] = nil;  sieve[p4] = nil
 121  	     sieve[p5] = nil;  sieve[p6] = nil;  sieve[p7] = nil;  sieve[p8] = nil
 122  	     p1 += k; p2 += k; p3 += k; p4 += k; p5 += k; p6 += k; p7 += k; p8 += k
 123  	 end
 124        end
 125        sieve.compact!
 126     end
 127  
 128     def primesP5a
 129        # all prime candidates > 5 are of form  30*k+(1,7,11,13,17,19,23,29)
 130        # initialize sieve array with only these candidate values
 131        # where sieve contains the odd integers representatives
 132        # convert integers to array indices/vals by  i = (n-3)>>1 = n>>1 - 1
 133        n1, n2, n3, n4, n5, n6, n7, n8 = -1, 2, 4, 5, 7, 8, 10, 13
 134        lndx= (self-1) >>1;  sieve = []
 135        while n8 < lndx
 136           n1 +=15;   n2 += 15;   n3 += 15;   n4 += 15
 137  	 n5 +=15;   n6 += 15;   n7 += 15;   n8 += 15
 138  	 sieve[n1] = n1;  sieve[n2] = n2;  sieve[n3] = n3;  sieve[n4] = n4
 139  	 sieve[n5] = n5;  sieve[n6] = n6;  sieve[n7] = n7;  sieve[n8] = n8
 140        end
 141        # now initialize sieve with the (odd) primes < 30, resize array
 142        sieve[0]=0;  sieve[1]=1;  sieve[2]=2;  sieve[4]=4;  sieve[5]=5
 143        sieve[7]=7;  sieve[8]=8;  sieve[10]=10;  sieve[13]=13
 144        sieve = sieve[0..lndx-1]
 145  
 146        7.step(Math.sqrt(self).to_i, 2) do |i|
 147           next unless sieve[(i>>1) - 1]
 148  	 # p1=7*i, p2=11*i, p3=13*i ---- p6=23*i, p7=29*i, p8=31*i,  k=30*i
 149  	 # maps to: p1= (7*i-3)>>1, --- p8=(31*i-3)>>1, k=30*i>>1
 150  	 n2=i<<1;  n4=i<<2;  n8=i<<3;  n16=i<<4;  n32=i<<5;  n12=n8+n4
 151  	 p1 = (n8-i-3)>>1;  p2 = (n12-i-3)>>1;  p3 = (n12+i-3)>>1;  p4 = (n16+i-3)>>1
 152  	 p5 = (n16+n4-i-3)>>1;  p6 = (n16+n8-i-3)>>1;  p7 = (n32-n4+i-3)>>1
 153  	 p8 = (n32-i-3)>>1;  k = (n32-n2)>>1
 154  	 while p1 < lndx
 155  	     sieve[p1] = nil;  sieve[p2] = nil;  sieve[p3] = nil;  sieve[p4] = nil
 156  	     sieve[p5] = nil;  sieve[p6] = nil;  sieve[p7] = nil;  sieve[p8] = nil
 157  	     p1 += k;  p2 += k;  p3 += k;  p4 += k;  p5 += k;  p6 += k;  p7 += k;  p8 += k
 158  	 end
 159        end
 160        return [2] if self < 3
 161        [2]+([nil]+sieve).compact!.map {|i| (i<<1) +3 }
 162     end
 163  
 164     def primesP7
 165        # all prime candidates > 7 are of form  210*k+(1,11,13,17,19,23,29,31,37
 166        # 41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,121,127,131
 167        # 137,139,143,149,151,157,163,167,169,173,179,181,187,191,193,197,199,209)
 168        # initialize sieve array with only these candidate values
 169        n1, n2, n3, n4, n5, n6, n7, n8, n9, n10 = 1, 11, 13, 17, 19, 23, 29, 31, 37, 41
 170        n11, n12, n13, n14, n15, n16, n17, n18 = 43, 47, 53, 59, 61, 67, 71, 73
 171        n19, n20, n21, n22, n23, n24, n25, n26 = 79, 83, 89, 97, 101, 103, 107, 109
 172        n27, n28, n29, n30, n31, n32, n33, n34 = 113, 127, 131, 137, 139, 149, 151, 157
 173        n35, n36, n37, n38, n39, n40, n41, n42, n43 = 163, 167, 173, 179, 181, 191, 193, 197, 199
 174        n44, n45, n46, n47, n48 = 121, 143, 169, 187,  209
 175        num = self - self[0]^1;  sieve = []
 176        while n48 < num
 177           n1  +=210;  n2  += 210;  n3  += 210;  n4  += 210;  n5  += 210
 178  	 n6  +=210;  n7  += 210;  n8  += 210;  n9  += 210;  n10 += 210
 179           n11 +=210;  n12 += 210;  n13 += 210;  n14 += 210;  n15 += 210
 180  	 n16 +=210;  n17 += 210;  n18 += 210;  n19 += 210;  n20 += 210
 181           n21 +=210;  n22 += 210;  n23 += 210;  n24 += 210;  n25 += 210
 182  	 n26 +=210;  n27 += 210;  n28 += 210;  n29 += 210;  n30 += 210
 183           n31 +=210;  n32 += 210;  n33 += 210;  n34 += 210;  n35 += 210
 184  	 n36 +=210;  n37 += 210;  n38 += 210;  n39 += 210;  n40 += 210
 185  	 n41 +=210;  n42 += 210; n43 += 210; n44 += 210; n45 += 210 
 186  	 n46 += 210; n47 += 210; n48 += 210
 187  	 sieve[n1] = n1;    sieve[n2]  = n2;   sieve[n3] = n3;    sieve[n4] = n4
 188  	 sieve[n5] = n5;    sieve[n6]  = n6;   sieve[n7] = n7;    sieve[n8] = n8
 189  	 sieve[n9] = n9;    sieve[n10] = n10;  sieve[n11] = n11;  sieve[n12] = n12
 190  	 sieve[n13] = n13;  sieve[n14] = n14;  sieve[n15] = n15;  sieve[n16] = n16
 191  	 sieve[n17] = n17;  sieve[n18] = n18;  sieve[n19] = n19;  sieve[n20] = n20
 192  	 sieve[n21] = n21;  sieve[n22] = n22;  sieve[n23] = n23;  sieve[n24] = n24
 193  	 sieve[n25] = n25;  sieve[n26] = n26;  sieve[n27] = n27;  sieve[n28] = n28
 194  	 sieve[n29] = n29;  sieve[n30] = n30;  sieve[n31] = n31;  sieve[n32] = n32
 195  	 sieve[n33] = n33;  sieve[n34] = n34;  sieve[n35] = n35;  sieve[n36] = n36
 196  	 sieve[n37] = n37;  sieve[n38] = n38;  sieve[n39] = n39;  sieve[n40] = n40
 197  	 sieve[n41] = n41;  sieve[n42] = n42;  sieve[n43] = n43;  sieve[n44] = n44
 198           sieve[n45] = n44;  sieve[n46] = n46;  sieve[n47] = n47;  sieve[n48] = n48
 199        end
 200        # now initialize sieve with the (odd) primes < 210, resize array
 201        sieve[2]=2;  sieve[3]=3;  sieve[5]=5;  sieve[7]=7;  sieve[11]=11;  sieve[13]=13
 202        sieve[17]=17;   sieve[19]=19;   sieve[23]=23;   sieve[29]=29;   sieve[31]=31
 203        sieve[37]=37;   sieve[41]=41;   sieve[43]=43;   sieve[47]=47;   sieve[53]=53
 204        sieve[59]=59;   sieve[61]=61;   sieve[67]=67;   sieve[71]=71;   sieve[73]=73
 205        sieve[79]=79;   sieve[83]=83;   sieve[89]=89;   sieve[97]=97;   sieve[101]=101
 206        sieve[103]=103; sieve[107]=107; sieve[109]=109; sieve[113]=113; sieve[127]=127
 207        sieve[131]=131; sieve[137]=137; sieve[139]=139; sieve[149]=149; sieve[151]=151
 208        sieve[157]=157; sieve[163]=163; sieve[167]=167; sieve[173]=173; sieve[179]=179
 209        sieve[181]=181; sieve[191]=191; sieve[193]=193; sieve[197]=197; sieve[199]=199
 210        sieve = sieve[0..self]
 211        11.step(Math.sqrt(self).to_i, 2) do |i|
 212           next unless sieve[i]
 213  	 # p1=7*i, p2=11*i, p3=13*i ---- p6=23*i, p7=29*i, p8=31*i,  k=30*i
 214  	 # maps to: p1= (7*i-3)>>1, --- p8=(31*i)>>1, k=30*i>>1
 215  	 #n6=6*i;  n7=n6+i;  n11=n6+n6-i;  n13=n6+n7;  n17=n11+n6
 216  	 #n19=n13+n6;  n23=n17+n6;  n29=n23+n6;  n31=n29+(i<<1)
 217  	 #n4=i<<2;  n8=i<<3;  n16=i<<4;  n7=n8-i;  n11=n7+n4;  n13=n11+(i<<1)
 218  	 #n17=n16+i;  n19=n11+n8;  n23=n16+n7;  n29=n16+n13;  n31=(i<<5)-i
 219  	 p1 = (11*i);   p2 = (13*i);   p3 = (17*i);   p4 = (19*i)  
 220  	 p5 = (23*i);   p6 = (29*i);   p7 = (31*i);   p8 = (37*i) 
 221  	 p9 = (41*i);   p10 = (43*i);  p11 = (47*i);  p12 = (53*i) 
 222  	 p13 = (59*i);  p14 = (61*i);  p15 = (67*i);  p16 = (71*i) 
 223  	 p17 = (73*i);  p18 = (79*i);  p19 = (83*i);  p20 = (89*i) 
 224           p21 = (97*i);  p22 = (101*i); p23 = (103*i); p24 = (107*i) 
 225  	 p25 = (109*i); p26 = (113*i); p27 = (127*i); p28 = (131*i) 
 226  	 p29 = (137*i); p30 = (139*i); p31 = (149*i); p32 = (151*i) 
 227  	 p33 = (157*i); p34 = (163*i); p35 = (167*i); p36 = (173*i) 
 228  	 p37 = (179*i); p38 = (181*i); p39 = (191*i); p40 = (193*i) 
 229  	 p41 = (197*i); p42 = (199*i); p43 = (211*i)
 230  	 p44 = (121*i); p45 = 143*i;  p46 = 169*i; p47 = 187*i; p48 = 209*i
 231  	 k = (210*i) 
 232  	 while p1 <= num
 233  	     sieve[p1] = nil;   sieve[p2] = nil;   sieve[p3] = nil;   sieve[p4] = nil
 234  	     sieve[p5] = nil;   sieve[p6] = nil;   sieve[p7] = nil;   sieve[p8] = nil
 235  	     sieve[p9] = nil;   sieve[p10] = nil;  sieve[p11] = nil;  sieve[p12] = nil
 236  	     sieve[p13] = nil;  sieve[p14] = nil;  sieve[p15] = nil;  sieve[p16] = nil
 237  	     sieve[p17] = nil;  sieve[p18] = nil;  sieve[p19] = nil;  sieve[p20] = nil
 238  	     sieve[p21] = nil;  sieve[p22] = nil;  sieve[p23] = nil;  sieve[p24] = nil
 239  	     sieve[p25] = nil;  sieve[p26] = nil;  sieve[p27] = nil;  sieve[p28] = nil
 240  	     sieve[p29] = nil;  sieve[p30] = nil;  sieve[p31] = nil;  sieve[p32] = nil
 241  	     sieve[p33] = nil;  sieve[p34] = nil;  sieve[p35] = nil;  sieve[p36] = nil
 242  	     sieve[p37] = nil;  sieve[p38] = nil;  sieve[p39] = nil;  sieve[p40] = nil
 243  	     sieve[p41] = nil;  sieve[p42] = nil;  sieve[p43] = nil;  sieve[p44] = nil
 244               sieve[p45] = nil;  sieve[p46] = nil;  sieve[p47] = nil;  sieve[p48] = nil
 245  	     p1 += k;  p2 += k; p3 += k; p4  += k; p5  +=k; p6 += k; p7 += k
 246  	     p8 += k;  p9 += k; p10 +=k; p11 += k; p12 +=k; p13 +=k; p14 +=k
 247  	     p15 +=k;  p16 +=k; p17 +=k; p18 += k; p19 +=k; p20 +=k; p21 +=k
 248  	     p22 +=k;  p23 +=k; p24 +=k; p25 += k; p26 +=k; p27 +=k; p28 +=k
 249  	     p29 +=k;  p30 +=k; p31 +=k; p32 += k; p33 +=k; p34 +=k; p35 +=k
 250  	     p36 +=k;  p37 +=k; p38 +=k; p39 += k; p40 +=k; p41 +=k; p42 +=k
 251               p43 +=k;  p44 +=k; p45 +=k; p46 +=k;  p47 +=k; p48 +=k
 252  	 end
 253        end
 254        sieve.compact! 
 255     end
 256  
 257     def primesP7a
 258        # all prime candidates > 7 are of form  210*k+(1,11,13,17,19,23,29,31,37
 259        # 41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,121,127,131
 260        # 137,139,143,149,151,157,163,167,169173,179,181,187,191,193,197,199,209)
 261        # initialize sieve array with only these candidate values
 262        # where sieve contains the odd integers representatives
 263        # convert integers to array indices/vals by  i = (n )>>1 = (n>>1)-1
 264        n1, n2, n3, n4, n5, n6, n7, n8, n9, n10 = -1, 4, 5, 7, 8, 10, 13, 14, 17, 19
 265        n11, n12, n13, n14, n15, n16, n17, n18 = 20, 22, 25, 28, 29, 32, 34, 35
 266        n19, n20, n21, n22, n23, n24, n25, n26 = 38, 40, 43, 47, 49, 50, 52, 53
 267        n27, n28, n29, n30, n31, n32, n33, n34 = 55, 62, 64, 67, 68, 73, 74, 77
 268        n35, n36, n37, n38, n39, n40, n41, n42, n43 = 80, 82, 85, 88, 89, 94, 95, 97, 98
 269        n44, n45, n46, n47, n48 = 59, 70, 83, 92, 103
 270        lndx= (self-1)>>1;  sieve = []
 271        while n48 < lndx
 272           n1 +=105;   n2 += 105;   n3 += 105;   n4 += 105;   n5 += 105
 273  	 n6 +=105;   n7 += 105;   n8 += 105;   n9 += 105;   n10 += 105
 274           n11 +=105;  n12 += 105;  n13 += 105;  n14 += 105;  n15 += 105
 275  	 n16 +=105;  n17 += 105;  n18 += 105;  n19 += 105;  n20 += 105
 276           n21 +=105;  n22 += 105;  n23 += 105;  n24 += 105;  n25 += 105
 277  	 n26 +=105;  n27 += 105;  n28 += 105;  n29 += 105;  n30 += 105
 278           n31 +=105;  n32 += 105;  n33 += 105;  n34 += 105;  n35 += 105
 279  	 n36 +=105;  n37 += 105;  n38 += 105;  n39 += 105;  n40 += 105
 280  	 n41 +=105;  n42 += 105;  n43 += 105;  n44 += 105;  n45 += 105
 281  	 n46 +=105;  n47 += 105;  n48 += 105
 282  	 sieve[n1] = n1;    sieve[n2] = n2;    sieve[n3] = n3;    sieve[n4] = n4
 283  	 sieve[n5] = n5;    sieve[n6] = n6;    sieve[n7] = n7;    sieve[n8] = n8
 284  	 sieve[n9] = n9;    sieve[n10] = n10;  sieve[n11] = n11;  sieve[n12] = n12
 285  	 sieve[n13] = n13;  sieve[n14] = n14;  sieve[n15] = n15;  sieve[n16] = n16
 286  	 sieve[n17] = n17;  sieve[n18] = n18;  sieve[n19] = n19;  sieve[n20] = n20
 287  	 sieve[n21] = n21;  sieve[n22] = n22;  sieve[n23] = n23;  sieve[n24] = n24
 288  	 sieve[n25] = n25;  sieve[n26] = n26;  sieve[n27] = n27;  sieve[n28] = n28
 289  	 sieve[n29] = n29;  sieve[n30] = n30;  sieve[n31] = n31;  sieve[n32] = n32
 290  	 sieve[n33] = n33;  sieve[n34] = n34;  sieve[n35] = n35;  sieve[n36] = n36
 291  	 sieve[n37] = n37;  sieve[n38] = n38;  sieve[n39] = n39;  sieve[n40] = n40
 292  	 sieve[n41] = n41;  sieve[n42] = n42;  sieve[n43] = n43;  sieve[n44] = n44 
 293  	 sieve[n45] = n45;  sieve[n46] = n46;  sieve[n47] = n47;  sieve[n48] = n48
 294        end
 295        # now initialize sieve with the (odd) primes < 210, resize array
 296        sieve[0]=0;    sieve[1]=1;    sieve[2]=2;    sieve[4]=4;    sieve[5]=5
 297        sieve[7]=7;    sieve[8]=8;    sieve[10]=10;  sieve[13]=13;  sieve[14]=14
 298        sieve[17]=17;  sieve[19]=19;  sieve[20]=20;  sieve[22]=22;  sieve[25]=25
 299        sieve[28]=28;  sieve[29]=29;  sieve[32]=32;  sieve[34]=34;  sieve[35]=35
 300        sieve[38]=38;  sieve[40]=40;  sieve[43]=43;  sieve[47]=47;  sieve[49]=49
 301        sieve[50]=50;  sieve[52]=52;  sieve[53]=53;  sieve[55]=55;  sieve[62]=62
 302        sieve[64]=64;  sieve[67]=67;  sieve[68]=68;  sieve[73]=73;  sieve[74]=74
 303        sieve[77]=77;  sieve[80]=80;  sieve[82]=82;  sieve[85]=85;  sieve[88]=88
 304        sieve[89]=89;  sieve[94]=94;  sieve[95]=95;  sieve[97]=97;  sieve[98]=98; 
 305        sieve = sieve[0..lndx-1]
 306  
 307        11.step(Math.sqrt(self).to_i, 2) do |i|
 308           next unless sieve[(i>>1) - 1]
 309  	 # p1=7*i, p2=11*i, p3=13*i ---- p6=23*i, p7=29*i, p8=31*i,  k=30*i
 310  	 # maps to: p1= (7*i-3)>>1, --- p8=(31*i)>>1, k=30*i>>1
 311  	 #n6=6*i;  n7=n6+i;  n11=n6+n6-i;  n13=n6+n7;  n17=n11+n6
 312  	 #n19=n13+n6;  n23=n17+n6;  n29=n23+n6;  n31=n29+(i<<1)
 313  	 #n4=i<<2;  n8=i<<3;  n16=i<<4;  n7=n8-i;  n11=n7+n4;  n13=n11+(i<<1)
 314  	 #n17=n16+i;  n19=n11+n8;  n23=n16+n7;  n29=n16+n13;  n31=(i<<5)-i
 315  	 p1 = (11*i-3)>>1;   p2 = (13*i-3)>>1;   p3 = (17*i-3)>>1;   p4 = (19*i-3)>>1
 316  	 p5 = (23*i-3)>>1;   p6 = (29*i-3)>>1;   p7 = (31*i-3)>>1;   p8 = (37*i-3)>>1
 317  	 p9 = (41*i-3)>>1;   p10 = (43*i-3)>>1;  p11 = (47*i-3)>>1;  p12 = (53*i-3)>>1
 318  	 p13 = (59*i-3)>>1;  p14 = (61*i-3)>>1;  p15 = (67*i-3)>>1;  p16 = (71*i-3)>>1
 319  	 p17 = (73*i-3)>>1;  p18 = (79*i-3)>>1;  p19 = (83*i-3)>>1;  p20 = (89*i-3)>>1
 320           p21 = (97*i-3)>>1;  p22 = (101*i-3)>>1; p23 = (103*i-3)>>1; p24 = (107*i-3)>>1
 321  	 p25 = (109*i-3)>>1; p26 = (113*i-3)>>1; p27 = (127*i-3)>>1; p28 = (131*i-3)>>1
 322  	 p29 = (137*i-3)>>1; p30 = (139*i-3)>>1; p31 = (149*i-3)>>1; p32 = (151*i-3)>>1
 323  	 p33 = (157*i-3)>>1; p34 = (163*i-3)>>1; p35 = (167*i-3)>>1; p36 = (173*i-3)>>1
 324  	 p37 = (179*i-3)>>1; p38 = (181*i-3)>>1; p39 = (191*i-3)>>1; p40 = (193*i-3)>>1
 325  	 p41 = (197*i-3)>>1; p42 = (199*i-3)>>1; p43 = (211*i-3)>>1; p44 = (121*i-3)>>1
 326  	 p45 = (143*i-3)>>1; p46 = (169*i-3)>>1; p47 = (187*i-3)>>1; p48 = (209*i-3)>>1
 327  	 k = (210*i)>>1
 328  	 while p1 < lndx
 329  	     sieve[p1] = nil;   sieve[p2] = nil;   sieve[p3] = nil;   sieve[p4] = nil
 330  	     sieve[p5] = nil;   sieve[p6] = nil;   sieve[p7] = nil;   sieve[p8] = nil
 331  	     sieve[p9] = nil;   sieve[p10] = nil;  sieve[p11] = nil;  sieve[p12] = nil
 332  	     sieve[p13] = nil;  sieve[p14] = nil;  sieve[p15] = nil;  sieve[p16] = nil
 333  	     sieve[p17] = nil;  sieve[p18] = nil;  sieve[p19] = nil;  sieve[p20] = nil
 334  	     sieve[p21] = nil;  sieve[p22] = nil;  sieve[p23] = nil;  sieve[p24] = nil
 335  	     sieve[p25] = nil;  sieve[p26] = nil;  sieve[p27] = nil;  sieve[p28] = nil
 336  	     sieve[p29] = nil;  sieve[p30] = nil;  sieve[p31] = nil;  sieve[p32] = nil
 337  	     sieve[p33] = nil;  sieve[p34] = nil;  sieve[p35] = nil;  sieve[p36] = nil
 338  	     sieve[p37] = nil;  sieve[p38] = nil;  sieve[p39] = nil;  sieve[p40] = nil
 339  	     sieve[p41] = nil;  sieve[p42] = nil;  sieve[p43] = nil;  sieve[p44] =nil
 340  	     sieve[p45] = nil;  sieve[p46] = nil;  sieve[p47] = nil;  sieve[p48] =nil
 341  	     p1 += k; p2 += k; p3 += k; p4  += k; p5 += k; p6 += k; p7 += k
 342  	     p8 += k; p9 += k; p10 +=k; p11 += k; p12 +=k; p13 +=k; p14 +=k
 343  	     p15 +=k; p16 +=k; p17 +=k; p18 += k; p19 +=k; p20 +=k; p21 +=k
 344  	     p22 +=k; p23 +=k; p24 +=k; p25 += k; p26 +=k; p27 +=k; p28 +=k
 345  	     p29 +=k; p30 +=k; p31 +=k; p32 += k; p33 +=k; p34 +=k; p35 +=k
 346  	     p36 +=k; p37 +=k; p38 +=k; p39 += k; p40 +=k; p41 +=k; p42 +=k
 347  	     p43 +=k; p44 +=k; p45 +=k; p46 += k; p47 +=k; p48 +=k
 348  	 end
 349        end
 350        return [2] if self < 3
 351        [2]+([nil]+sieve).compact!.map {|i| (i<<1) +3 }
 352     end
 353     
 354     def primesP60
 355        # all prime candidates > 5 are of form  60*k+(1,7,11,13,17,19,23,29,
 356        # 31,37,41,43,47,49,53,59
 357        # initialize sieve array with only these candidate values
 358        n1, n2, n3, n4, n5, n6, n7, n8, n9, n10 = 1, 7, 11, 13, 17, 19, 23, 29, 31, 37
 359        n11, n12, n13, n14, n15, n16 = 41, 43, 47, 49, 53, 59
 360        num = self - self[0]^1;  sieve = []
 361        while n16 < num
 362           n1 += 60;   n2 += 60;   n3 += 60;   n4 += 60;   n5 += 60
 363  	 n6 += 60;   n7 += 60;   n8 += 60;   n9 += 60;   n10 += 60
 364           n11 += 60;  n12 += 60;  n13 += 60;  n14 += 60;  n15 += 60;  n16 += 60
 365  	 sieve[n1] = n1;  sieve[n2] = n2;  sieve[n3] = n3;  sieve[n4] = n4
 366  	 sieve[n5] = n5;  sieve[n6] = n6;  sieve[n7] = n7;  sieve[n8] = n8
 367  	 sieve[n9] = n9;  sieve[n10] = n10;  sieve[n11] = n11;  sieve[n12] = n12
 368  	 sieve[n13] = n13; sieve[n14] = n14; sieve[n15] = n15;  sieve[n16] = n16
 369        end
 370        # now initialize sieve with the (odd) primes < 210, resize array
 371        sieve[2]=2;  sieve[3]=3;  sieve[5]=5;  sieve[7]=7;  sieve[11]=11;  sieve[13]=13
 372        sieve[17]=17;  sieve[19]=19;  sieve[23]=23;  sieve[29]=29;  sieve[31]=31
 373        sieve[37]=37; sieve[41]=41; sieve[43]=43; sieve[47]=47; sieve[53]=53; sieve[59]=59
 374        sieve = sieve[0..self]
 375        7.step(Math.sqrt(self).to_i, 2) do |i|
 376           next unless sieve[i]
 377  	 # p1=7*i, p2=11*i, p3=13*i ---- p6=23*i, p7=29*i, p8=31*i,  k=30*i
 378  	 # maps to: p1= (7*i-3)>>1, --- p8=(31*i)>>1, k=30*i>>1
 379  	 #n6=6*i;  n7=n6+i;  n11=n6+n6-i;  n13=n6+n7;  n17=n11+n6
 380  	 #n19=n13+n6;  n23=n17+n6;  n29=n23+n6;  n31=n29+(i<<1)
 381  	 #n4=i<<2;  n8=i<<3;  n16=i<<4;  n7=n8-i;  n11=n7+n4;  n13=n11+(i<<1)
 382  	 #n17=n16+i;  n19=n11+n8;  n23=n16+n7;  n29=n16+n13;  n31=(i<<5)-i
 383  	 p1 = 7*i;  p2 = 11*i;  p3 = 13*i;  p4 = 17*i;  p5= 19*i; p6 = 23*i;  p7 = 29*i
 384  	 p8 = 31*i;  p9 = 37*i; p10 = 41*i;  p11 = 43*i; p12 = 47*i; p13 = 53*i; p14 = 59*i
 385  	 p15 = 49*i;  p16 = 61*i; k = 60*i
 386  	 
 387  	 #n2 = i<<1;  n4 = i<<2;  n8 = i<<3;  n16 = i<<4;  n32 = i<<5;  n64 = i<<6
 388  	 #p1 = n8-i;  p2 = n8+n4-i;  p3 = n8+n4+i;  p4 = n16+i;  p5 = n16+n2+i;  p6 = n16+n8-i
 389  	 #p7 = n32-n2-i;  p8 = n32-i;  p9=n32+n4+i;  p10=n32+n8+i;  p11=p2+n32;  p12=n32+n16-i
 390  	 #p13 = p9+n16;  p14 = n64-n4-i;  p15 = n64-n16+i;  p16 = n64-n2-i;  k = n64-n4
 391  	 while p1 < num
 392  	     sieve[p1] = nil;  sieve[p2] = nil;   sieve[p3] = nil;  sieve[p4] = nil
 393  	     sieve[p5] = nil;  sieve[p6] = nil;   sieve[p7] = nil;  sieve[p8] = nil
 394  	     sieve[p9] = nil;  sieve[p10] = nil;  sieve[p11] = nil; sieve[p12] = nil
 395  	     sieve[p13] = nil;  sieve[p14] = nil; sieve[p15] = nil; sieve[p16] = nil
 396  	     p1 += k;  p2 += k;  p3 += k;  p4 += k;  p5 += k; p6 += k; p7 += k; p16 +=k
 397  	     p8 += k;  p9 += k; p10 += k; p11 += k; p12 += k; p13 +=k; p14 +=k; p15 +=k
 398  	 end
 399        end
 400        sieve.compact! 
 401     end
 402    
 403     def primesP60a
 404        # all prime candidates > 5 are of form  60*k+(1,7,11,13,17,19,23,29,
 405        # 31,37,41,43,47,49,53,59
 406        # initialize sieve array with only these candidate values
 407        # where sieve contains the odd integers representatives
 408        # convert integers to array indices/vals by  i = (n-3)>>1 = (n>>1)-1
 409        n1, n2, n3, n4, n5, n6, n7, n8, n9, n10 = -1, 2, 4, 5, 7, 8, 10, 13, 14, 17
 410        n11, n12, n13, n14, n15, n16 = 19, 20, 22, 23, 25, 28
 411        lndx= (self-1) >>1;  sieve = []
 412        while n16 < lndx
 413           n1 += 30;   n2 += 30;   n3 += 30;   n4 += 30;   n5 += 30
 414  	 n6 += 30;   n7 += 30;   n8 += 30;   n9 += 30;   n10 += 30
 415           n11 += 30;  n12 += 30;  n13 += 30;  n14 += 30;  n15 += 30;  n16 += 30
 416  	 sieve[n1] = n1;  sieve[n2] = n2;  sieve[n3] = n3;  sieve[n4] = n4
 417  	 sieve[n5] = n5;  sieve[n6] = n6;  sieve[n7] = n7;  sieve[n