Loading ...
Sorry, an error occurred while loading the content.
 

Implementing Fermat prime number Sieve

Expand Messages
  • Kermit Rose
    I ve programmed the Fermat prime number sieve and tested it out on a few different ranges. If the occasion ever arose to factor all numbers in an interval,
    Message 1 of 1 , Jul 31, 2007
      I've programmed the Fermat prime number sieve and tested it out on a few
      different ranges.


      If the occasion ever arose to factor all numbers in an interval, this
      algorithm could be extended to find factors for all the numbers in the
      interval almost as quickly as Fermat factoring could factor the most
      difficult number in the interval.


      >>> SieveFermat(10**3,10**3+100)

      number of clears is 260
      [0, 0, 0, 0, 0, 0, 0, 0, 0, 1009, 0, 0, 0, 1013, 0, 0, 0, 0, 0, 1019, 0,
      1021, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1031, 0, 1033, 0, 0, 0, 0, 0, 1039, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 1049, 0, 1051, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1061,
      0, 1063, 0, 0, 0, 0, 0, 1069, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 1087, 0, 0, 0, 1091, 0, 1093, 0, 0, 0, 1097, 0, 0, 0]



      >>> SieveFermat(10**4,10**4+100)

      number of clears is 2135
      [0, 0, 0, 0, 0, 0, 0, 10007, 0, 10009, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10037, 0, 10039, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10061, 0, 0, 0,
      0, 0, 10067, 0, 10069, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10079, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 10091, 0, 10093, 0, 0, 0, 0, 0, 10099, 0]



      >>> SieveFermat(10**5,10**5+100)

      number of clears is 21255
      [0, 0, 0, 100003, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100019,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      100043, 0, 0, 0, 0, 0, 100049, 0, 0, 0, 0, 0, 0, 0, 100057, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 100069, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]



      >>> SieveFermat(10**6,10**6+100)

      number of clears is 213878
      [0, 0, 0, 1000003, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1000033, 0, 0, 0, 1000037, 0, 1000039,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1000081, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1000099, 0]



      >>> SieveFermat(10**5,10**5+1000)

      number of clears is 22491
      [0, 0, 0, 100003, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100019,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      100043, 0, 0, 0, 0, 0, 100049, 0, 0, 0, 0, 0, 0, 0, 100057, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 100069, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100103, 0, 0,
      0, 0, 0, 100109, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 100129, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 100151, 0, 100153, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      100169, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100183, 0, 0, 0, 0, 0,
      100189, 0, 0, 0, 100193, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100207,
      0, 0, 0, 0, 0, 100213, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 100237, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100267, 0, 0, 0, 100271, 0,
      0, 0, 0, 0, 0, 0, 100279, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100291, 0, 0,
      0, 0, 0, 100297, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100313, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100333, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 100343, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100357,
      0, 0, 0, 100361, 0, 100363, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      100379, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100391, 0, 100393, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 100403, 0, 0, 0, 0, 0, 0, 0, 100411, 0, 0, 0, 0, 0,
      100417, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 100447, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100459,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 100469, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 100483, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100493, 0, 0, 0, 0, 0, 0, 0,
      100501, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100511, 0, 0, 0, 0, 0, 100517, 0,
      100519, 0, 0, 0, 100523, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100537,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 100547, 0, 100549, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      100559, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100591, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 100609, 0, 0, 0, 100613, 0, 0, 0, 0, 0, 0, 0, 100621,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 100649, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 100669, 0, 0, 0, 100673, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 100693, 0, 0, 0, 0, 0, 100699, 0, 0, 0, 100703, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 100733, 0, 0, 0, 0, 0, 0, 0, 100741, 0, 0, 0, 0, 0, 100747, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100769, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100787, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 100799, 0, 100801, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100811, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 100823, 0, 0, 0, 0, 0, 100829, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100847, 0, 0, 0, 0, 0, 100853, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 100907, 0, 0, 0, 0, 0, 100913, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 100927, 0, 0, 0, 100931, 0, 0, 0, 0, 0, 100937, 0, 0, 0, 0, 0,
      100943, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100957, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100981, 0, 0, 0, 0,
      0, 100987, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100999, 0]
      >>>


      Kermit < kermit@... >



      ----------

      def SieveFermat(start,end):
      rstart = ksqrt(start-1)
      if start == 0:
      rstart = -1
      rend = ksqrt(end)
      jar = range(start,end+1)

      plex = 0

      ##### zero out 1 if it is present

      if start < 2:
      jar[1 - start] = 0

      #### zero out all even numbers

      mds = start + start%2
      mde = end + end%2
      while mds < mde + 1:
      jar[mds - start] = 0
      mds = mds + 2


      ##### outer loop : Set larger square for difference of squares

      rs = rstart + 0
      if rs < 2:
      rs = 2
      rsupper = (end + 10)/6
      while rs < rsupper:
      rs = rs + 1
      rs2 = rs * rs
      if rs2 < start:
      continue

      ####### set smaller square for difference of squares. Difference must be odd number.

      loop2 = 0
      sidelow = rs2 - end
      if sidelow < 1:
      sidelow = 1
      sidehigh = rs2 - start + 1
      dexlow = ksqrt(sidelow - 1)
      dexhigh = ksqrt(sidehigh - 1)
      if dexhigh > rs -4:
      dexhigh = rs - 4
      dex = dexlow - dexlow%2 -rs%2 -1

      ##### dex remains opposite parity from rs

      while dex < dexhigh:
      dex = dex + 2

      plex = plex + 1

      dex2 = dex * dex
      d1 = rs - dex
      if d1 < 2:
      break
      d2 = rs2 - dex2
      if d2 < start:
      break
      if d2 > end:
      continue
      pos = d2 - start
      jar[pos] = 0

      print "\n number of clears is ",plex
      return jar



      def ksqrt(start):
      if start < 1:
      return 0
      r = 1
      r2 = r * r
      while r2 < start:
      r = r * 2
      r2 = r2 * 4
      s = 0
      s2 = 0
      while r > 0:
      s = s + r
      s2 = s * s
      if s2 > start:
      s = s - r
      r = r/2
      return s


      [Non-text portions of this message have been removed]
    Your message has been successfully submitted and would be delivered to recipients shortly.