## Prime Numbers

No need to worry about going "off topic" here
Forum rules
This forum is for general chit-chat, not necessarily APL-related. However, it's not for spam or for offensive or illegal comments.

### Prime Numbers

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 291 1 1 0 1 1 0 1 1 0 1 0 0 1      is_Prime 97463477721611`

I've got some nice Carmichael numbers around here somewhere
Code: Select all
`      isPrime¨1105 1729 2465 2821 6601 89110 0 0 0 0 0`

Enjoy.
Jane

Budgie

Posts: 36
Joined: Thu Nov 26, 2009 9:22 am
Location: Beckenham

### Re: Prime Numbers

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
Veli-Matti

Posts: 44
Joined: Sat Nov 28, 2009 3:12 pm

### Re: Prime Numbers

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

Budgie

Posts: 36
Joined: Thu Nov 26, 2009 9:22 am
Location: Beckenham