Speed up development with full-stack environments for every branch.

Learn More

Sieve Of Eratostene [Ruby]

Forked from Basic Ruby Example.

0 Runs 3 Views 0 Copies
Saved

Saved

Guildenstern70 3

Guildenstern70
published 2 years ago

#!/usr/bin/env ruby

#
# Compute prime numbers
# with the good old Eratostene Sieve method
# Author: Alessio Saltarin
#


# Eratostene Sieve computer class
class Sieve
    # Constructor
    # maxprime: max upper limit
    def initialize(maxprime)
            puts "Initializing sieve."
            @max = maxprime
            @sieve = Array.new
            @sieve[0] = 0
            @sieve[1] = 0
            for i in 2 ... @max
                    @sieve[i] = 1
            end
    end
    
    # Return a list of prime numbers
    def primes
            printf("Computing primes to %d ...\n", @max)
            crivello()
            puts "Done."
            retprimes = Array.new
            for k in 0..@max
                    if @sieve[k] == 1
                            retprimes.push(k)
                    end
            end
            return retprimes
    end
    
    # Sieve (Crivello) algorithm
    def crivello
            currprime = nextprime(0)
            while (currprime * currprime < @max)
                    i = currprime * currprime
                    while (i < @max)
                            @sieve[i] = 0
                            i += currprime
                    end
                    currprime = nextprime(currprime)
            end
    end

    # Return next prime
    # lastprime: the last computer prime number
    def nextprime(lastprime)
        
            for i in lastprime+1...@max
                    return i if @sieve[i] == 1
            end
    end
  
	
end

# Print a list of prime numbers
def printPrimes(primes)
    primes.each { |nr| printf("Prime: %d\n", nr) }
end

# Print the sum of prime numbers
def printSumPrimes(primes)
    sum = 0
    puts("Computing...")
    primes.each { |nr|  sum += nr }
    puts("Done.")
    printf("Prime Sum: %d\n", sum)
end

# Main
crivello = Sieve.new(1000000) # Compute primes for the first 1000000 natural numbers
printSumPrimes(crivello.primes)
Please login/signup to get access to the terminal.

Your session has timed out.

Dismiss (the page may not function properly).