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

Postby Budgie on Wed Jun 06, 2012 10:37 pm

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.
Jane
User avatar
Budgie
 
Posts: 36
Joined: Thu Nov 26, 2009 9:22 am
Location: Beckenham

Re: Prime Numbers

Postby Veli-Matti on Mon Jun 18, 2012 10:34 am

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

Postby Budgie on Thu Jun 21, 2012 4:25 pm

Sorry, I should have said that it only works on odd numbers.
Jane
User avatar
Budgie
 
Posts: 36
Joined: Thu Nov 26, 2009 9:22 am
Location: Beckenham


Return to Chat

Who is online

Users browsing this forum: No registered users and 1 guest