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

21252Primality testing - a newby

Expand Messages
  • William
    Jan 3, 2010
    • 0 Attachment
      I have divided the primes into 3 groups working on a general format of 36mn +/- 6m +/- 6n +/- 1.
      Below is a simple and I think efficient algorithm for testing 36mn+6m-6n-1 primes. The other two algorithms are similar.
      If it makes you groan at my stupidity then please direct me to somewhere where I can learn to be less dense.
      Otherwise - has it been done before?

      Let p be a potential prime p = 30a + b : b in {11,17,23,29}

      1. n = ((81+8p)^1/2 + 5)/24, rounded up to an integer
      c=n, r=2n-1
      q = ((24n-5)^2 -81)/8
      if q=p then p is r+- and not prime
      2. q = q - 36c - 42, r = r - 1
      if r=0 then p is prime
      if q=p then p is r+- and not prime
      if q > p then goto 2
      if q < p then goto 3
      3. q = q - 36r - 30, c = c - 1
      if c=0 then p is prime
      if q=p then p is r+- and not prime
      if q > p then an error has occurred
      if q < p then goto 4
      4. q = q + 36c + 42, r = r + 1
      if q=p then p is r+- and not prime
      if q > p then goto 5
      if q < p then goto 4
      5. q = q - 36r - 30, c = c - 1
      if c=0 then p is prime
      q = 36c - 42, r = r - 1
      if q=p then p is r+- and not prime
      if q > p then an error has occurred
      if q < p then goto 4
      I would appreciate your comments.
    • Show all 2 messages in this topic