How to resolve the algorithm Sieve of Eratosthenes step by step in the APL programming language

Published on 12 May 2024 09:40 PM
#Apl

How to resolve the algorithm Sieve of Eratosthenes step by step in the APL programming language

Table of Contents

Problem Statement

The Sieve of Eratosthenes is a simple algorithm that finds the prime numbers up to a given integer.

Implement the   Sieve of Eratosthenes   algorithm, with the only allowed optimization that the outer loop can stop at the square root of the limit, and the inner loop may start at the square of the prime just found. That means especially that you shouldn't optimize by using pre-computed wheels, i.e. don't assume you need only to cross out odd numbers (wheel based on 2), numbers equal to 1 or 5 modulo 6 (wheel based on 2 and 3), or similar wheels based on low primes. If there's an easy way to add such a wheel based optimization, implement it as an alternative version.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Sieve of Eratosthenes step by step in the APL programming language

Source code in the apl programming language

sieve2←{                          
  b←⍵⍴1             
  b[⍳2⌊⍵]←0         
  2≥⍵:b             
  p←{⍵/⍳⍴⍵}∇⌈⍵*0.5  
  m←1+⌊(⍵-1+p×p)÷p  
  b ⊣ p {b[⍺×⍺+⍳⍵]←0}¨ m
}

primes2←{⍵/⍳⍴⍵}∘sieve2


sieve←{                           
  b←⍵⍴{∧⌿↑(×/⍵)⍴¨~⍵↑¨1}2 3 5
  b[⍳6⌊⍵]←(6⌊⍵)⍴0 0 1 1 0 1 
  49≥⍵:b                    
  p←3↓{⍵/⍳⍴⍵}∇⌈⍵*0.5        
  m←1+⌊(⍵-1+p×p)÷2×p        
  b ⊣ p {b[⍺×⍺+2×⍳⍵]←0}¨ m      
}

primes←{⍵/⍳⍴⍵}∘sieve


   primes 100
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

   primes¨ ⍳14
┌┬┬┬─┬───┬───┬─────┬─────┬───────┬───────┬───────┬───────┬──────────┬──────────┐
││││2│2 3│2 3│2 3 5│2 3 5│2 3 5 7│2 3 5 7│2 3 5 7│2 3 5 7│2 3 5 7 11│2 3 5 7 11│
└┴┴┴─┴───┴───┴─────┴─────┴───────┴───────┴───────┴───────┴──────────┴──────────┘

   sieve 13
0 0 1 1 0 1 0 1 0 0 0 1 0

   +/∘sieve¨ 10*⍳10
0 4 25 168 1229 9592 78498 664579 5761455 50847534

You may also check:How to resolve the algorithm Boolean values step by step in the Clojure programming language
You may also check:How to resolve the algorithm Draw a sphere step by step in the Craft Basic programming language
You may also check:How to resolve the algorithm Tau number step by step in the PL/M programming language
You may also check:How to resolve the algorithm Queue/Usage step by step in the M2000 Interpreter programming language
You may also check:How to resolve the algorithm 9 billion names of God the integer step by step in the Dyalect programming language