Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Nsieve For Ruby

DZone's Guide to

Nsieve For Ruby

·
Free Resource
From: The Great Computer Language Shootout: nsieve-bits Ruby
Author: Glenn Parker



CharExponent = 3
BitsPerChar = 1 << CharExponent
LowMask = BitsPerChar - 1

def sieve(m)
  ret = []
  items = "\xFF" * ((m / BitsPerChar) + 1)
  masks = ""
  BitsPerChar.times do |b|
    masks << (1 << b).chr
  end

  count = 0
  pmax = m - 1
  2.step(pmax, 1) do |p|
    if items[p >> CharExponent][p & LowMask] == 1
      ret << p
      count += 1
      p.step(pmax, p) do |mult|
	a = mult >> CharExponent
	b = mult & LowMask
	items[a] -= masks[b] if items[a][b] != 0
        #p items
      end
    end
  end
  #count
  ret
end

n = (ARGV[0] || 2).to_i
n.step(n - 2, -1) do |exponent|
  break if exponent < 0
  m = 2 ** exponent * 10_000
  primes = sieve(m)
  count = primes.size
  puts
  printf "Primes up to %8d %8d\n", m, count
  puts "last ten primes: #{primes[-10..-1].join(' ')}"
  puts
end


Topics:

Opinions expressed by DZone contributors are their own.

THE DZONE NEWSLETTER

Dev Resources & Solutions Straight to Your Inbox

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.

X

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}