Escala | Tamiz de Eratóstenes

Eratóstenes de Cirene fue un matemático griego que descubrió un sorprendente algoritmo para encontrar números primos.

Este artículo realiza este algoritmo en Scala.

Paso 1 : Creando un flujo Int

def numberStream(n: Int): 
    Stream[Int] = Stream.from(n)
      
println(numberStream(10))

La salida del paso anterior es Stream(10, ?).

Paso 2: función de tamiz de Eratóstenes

// Defining Sieve of Eratosthenes
def sieve_of_Eratosthenes(stream: Stream[Int]): 
    Stream[Int] = stream.head #:: sieve_of_Eratosthenes(
        (stream.tail) 
        filter (x => x % stream.head != 0)
        )
          
println(sieve_of_Eratosthenes(numberStream(10)))

La salida del paso anterior es Stream(10, ?) .

Paso 3: Extraer el número «N» de números primos

val no_of_primes = sieve_of_Eratosthenes(numberStream(2))
  
// Selecting number of primes
println(no_of_primes)
(no_of_primes take 7) foreach { 
    println(_) 
    }

La salida del paso anterior es Stream(2, ?)
2
3
5
7
11
13
17 .

A continuación se muestra el programa completo.

def numberStream(n: Int): 
    Stream[Int] = Stream.from(n)
       
println(numberStream(10))
  
// Defining Sieve of Eratosthenes
def sieve_of_Eratosthenes(stream: Stream[Int]): 
    Stream[Int] = stream.head #:: sieve_of_Eratosthenes(
        (stream.tail) 
        filter (x => x % stream.head!= 0)
        )
           
println(sieve_of_Eratosthenes(numberStream(10)))
  
  
val no_of_primes = sieve_of_Eratosthenes(numberStream(2))
  
// Selecting number of primes 
println(no_of_primes)
(no_of_primes take 7) foreach { 
    println(_) 
    }

Producción:

Stream(10, ?)
Stream(10, ?)
Stream(2, ?)
2
3
5
7
11
13
17

Información del código

• Usando stream.form(), se crea una secuencia que genera números sucesivos. Y este número parte del argumento.
• Se le da un flujo de números al método «tamiz_de_Eratóstenes» . Este método, al filtrar los elementos, genera perezosamente los elementos sucesivos.

A continuación se muestra el código de trabajo completo con una explicación:

Funcionamiento: el método abc() inserta la declaración de depuración en el método filter() . Si un elemento no es divisible por la cabeza, la corriente lo trata como un buen elemento. El código lo imprime y devuelve verdadero. De lo contrario, se imprime la secuencia filtrada y finalmente se devuelve la secuencia.
Se realizan algunas modificaciones en el método sieve_of_Eratosthenes para utilizar el método de creación de secuencias – abc() . Los elementos se extraen del flujo recursivo y se imprimen.

object Sieve extends App {
    def abc(s: Stream[Int], head: Int) = { 
        val r = s filter {
            x => {
                if (x % head != 0) {
                    println()
                    println(s"${x} is not evenly divisible by ${head}")
                      
                    true
                    } 
                else {
                    println()
                    println(s"${x} is evenly divisible by ${head}. So Discard ${x}")
                false
                    }
                }
            }
        r
    }
    def numberStream(g: Int): Stream[Int] = Stream.from(g)
      
    def sieve_of_Eratosthenes(stream: Stream[Int]): 
    Stream[Int] = stream.head #:: sieve_of_Eratosthenes(
        abc(stream.tail, stream.head))
      
    val no_of_primes = sieve_of_Eratosthenes(numberStream(2))
    (no_of_primes take 7) foreach {
        println(_)
    }
}

Producción :

2

3 is not evenly divisible by 2
3

4 is evenly divisible by 2. So Discard 4

5 is not evenly divisible by 2

5 is not evenly divisible by 3
5

6 is evenly divisible by 2. So Discard 6

7 is not evenly divisible by 2

7 is not evenly divisible by 3

7 is not evenly divisible by 5
7

8 is evenly divisible by 2. So Discard 8

9 is not evenly divisible by 2

9 is evenly divisible by 3. So Discard 9

10 is evenly divisible by 2. So Discard 10

11 is not evenly divisible by 2

11 is not evenly divisible by 3

11 is not evenly divisible by 5

11 is not evenly divisible by 7
11

12 is evenly divisible by 2. So Discard 12

13 is not evenly divisible by 2

13 is not evenly divisible by 3

13 is not evenly divisible by 5

13 is not evenly divisible by 7

13 is not evenly divisible by 11
13

14 is evenly divisible by 2. So Discard 14

15 is not evenly divisible by 2

15 is evenly divisible by 3. So Discard 15

16 is evenly divisible by 2. So Discard 16

17 is not evenly divisible by 2

17 is not evenly divisible by 3

17 is not evenly divisible by 5

17 is not evenly divisible by 7

17 is not evenly divisible by 11

17 is not evenly divisible by 13
17