APL highly optimize prime number generator function

Let it all hang out

APL highly optimize prime number generator function

PostPosted by manandpc » Tue Jul 10, 2012 2:02 pm

The current implementation of 0π gives the primality test , so get all prime numbers up to N, you do:

⍸ 0π ⍳ N

Here (below) is a APL function that use highly optimize sieve algorithm and faster
Code: Select all
      ⎕cr'prime'
p ← prime n;d;i
d ← ⌊√n
p ← 0 1 1 0 1,(0⌈n-5) ⍴ 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0
:if n < 49
  p ← ⍸ n↑p
:else
  i ← 7
  :while 1
    p[ i× ¯1+i+ ⍸ p[ ¯1+i+ ⍳ 1+(⌊n÷i)-i ] ] ← 0
    i+ ← p[ i+ ⍳ ⌈i÷2 ] ⍳ 1
  :until i > d
  p ← ⍸ p
:endif

Here some tests:
Code: Select all
      ⎕ts ⋄ ⍴⍸ 0π ⍳ 10000000 ⋄ ⎕ts
2013 4 4 21 16 23 793
664579
2013 4 4 21 16 43 621
      ⎕ts ⋄ ⍴prime 10000000 ⋄ ⎕ts
2013 4 4 21 16 51 231
664579
2013 4 4 21 16 56 28
manandpc
 
Posts: 67
Joined: Tue Jun 19, 2012 9:39 am

Return to Open Discussion

Who is online

Users browsing this forum: No registered users and 1 guest

cron