Prime Numbers

[Budgie]

I came across this algorithm recently, and it seems only fair to let everyone else who may be interested have a look at it:

Code: Select all

      isPrime←{⌊(1+⌊3÷⍵)÷1++/⌊(k÷⍵)×⌊⍵÷k←1+2×(~⎕IO)+⍳⌊0.5×1+⍵*0.5}

      isPrime¨3 5 7 9 11 13 15 17 19 21 23 25 27 29
1 1 1 0 1 1 0 1 1 0 1 0 0 1
      is_Prime 9746347772161
1

I've got some nice Carmichael numbers around here somewhere

Code: Select all

      isPrime¨1105 1729 2465 2821 6601 8911
0 0 0 0 0 0

Enjoy.

[Veli-Matti]

Looks nice, but a quick exploring gives unexpected results:

isPrime←{⌊(1+⌊3÷⍵)÷1++/⌊(k÷⍵)×⌊⍵÷k←1+2×(~⎕IO)+⍳⌊0.5×1+⍵*0.5}
isPrime¨ 1 2 3 4 5 6 7 8 1004
4 2 1 1 1 0 1 1 1

Seemingly 1 and 2 are exceptions, but there seems to be problem with
even numbers, too. Fine-tuning the original expression seems to be
more convincing

isPrime←{(⍵<3)≥2|⍵:⍵=2 ⋄ ⍵{⌊(1+⌊3÷⍺)÷1++/⌊(⍵÷⍺)×⌊⍺÷⍵}1+2×(~⎕IO)+⍳⌊0.5×1+⍵*0.5}
0 1 1 0 1 0 1 0 0

Testing this against Roger Hui's pco function (in the dfns workspace) gives
quite good results. For example the only difference below one million is

⍬{⍵>1e6:⍺ ⋄ (isPrime ⍵)≠1 pco ⍵:(⍺,⍵) ∇ ⍵+2 ⋄ ⍺ ∇ ⍵+2}3
12769

-Veli-Matti

[Budgie]

Sorry, I should have said that it only works on odd numbers.