[ryuurei]

I suppose I'm rather late to the party here but I've been playing with Ruby a lot lately and thought I'd try my hand at my own sieve of Eratosthenes implementation.

require 'benchmark'

def eratosthenes(to_n)
  list = (2..to_n).to_a
  list.each do |n|
    (n..to_n).each {|x| list.delete(x) if x % n == 0 and x != n }
  end
  return list
end

thousand_sieve = eratosthenes(1000)
benchmark = Benchmark.realtime do
  1.upto(1000) do |n| 
    puts "#{n} is prime." if thousand_sieve.include? n
  end
end
puts "Time = %.5f seconds." %benchmark

[jace427]

Here's a simple solution, written as a method extending Integer.
The solution contains an unnecessary puts statement showing the number of iterations for comparison.
It is based on two precepts:

#1) Start with 2 and look for factors of N. Return false if you find any.
#2) Each time you increase your iterator by 1, reduce the comparison value to the maximum possible integer you could reach. (i.e. if your looking for factors of 127 and you start off with 2, then when 2 iterates to 3, you're not going to have to go past 42 (127/3), since doing so would imply a number less than 3 is a factor.)

I have included some iteration counts for certain integers compared to running through all the numbers between 1 and the original value divided by 2. Also, I know I don't need "return" in front of true, but I was being consistent since I do need it to break from the while loop properly.

class Integer
	def isprime?
		i = 2
		j = self
		while (i < j) do
			(self % i == 0) && (return false) 
			i += 1
			j = self / i
		end
		puts "Iterations: #{i-2}"
		return true
	end
end

Examples:
------PrimeNumber------ ------((N/2)-1)------- --isprime?-- Completion
                     17                      7           2   ~0.004s 
                     47                     22           5   ~0.008s
                     97                     47           8   ~0.008s
                    311                    154          16   ~0.008s
                  3,779                  1,888          59   ~0.008s
                 10,093                  5,045          98   ~0.010s
                115,249                 57,623         337   ~0.011s
                939,391                469,694         967   ~0.012s
            433,494,437            216,747,217      20,819   ~0.019s
         29,741,215,073         14,870,607,535     172,454   ~0.177s
     10,000,000,000,129      5,000,000,000,063   3,162,276   ~2.906s
 99,194,853,094,755,497 49,597,426,547,377,747 314,952,142   ~5m10.285s 

That last one is probably unacceptable, but you really have to get into the quadrillions before this algorithm starts to slow down.

Anyway, that my two cents.

Thanks,
jace427

[jace427]

Correction to account for numbers that are less than 2 which, by formal definition, are not prime; and to avoid infinite loops with such input.

class Integer
	def isprime?
		(self < 2) && (return false)
		i = 2
		j = self
		while (i < j) do
			(self % i == 0) && (return false) 
			i += 1
			j = self / i
		end
		puts "Iterations: #{i-2}"
		return true
	end
end

[RetardedGenius]

You should choose a set range of numbers or a specific number to make the speed comparisons fairer. To simply choose some arbitrary, large number is not enough. After all, any number with a small divisor will be found to be non-prime very quickly; even with a naive implementation.

To be more pedantic still: a distinction should be made between deterministic and probabilistic tests for primality. The fastest deterministic algorithm - that I am aware of - simply divides the number by all of the primes <= the square root of the number being tested; if a prime factor is found the number is non-prime. This algorithm however requires an array of precomputed primes making it unsuitable for applications such as RSA, which utilise massive primes.

Just my £0.02

[jace427]

RetardedGenius, on 01 November 2011 - 02:32 PM, said:

You should choose a set range of numbers or a specific number to make the speed comparisons fairer. To simply choose some arbitrary, large number is not enough. After all, any number with a small divisor will be found to be non-prime very quickly; even with a naive implementation.

To be more pedantic still: a distinction should be made between deterministic and probabilistic tests for primality. The fastest deterministic algorithm - that I am aware of - simply divides the number by all of the primes <= the square root of the number being tested; if a prime factor is found the number is non-prime. This algorithm however requires an array of precomputed primes making it unsuitable for applications such as RSA, which utilise massive primes.

Just my £0.02

Agreed, and perhaps I wasn't clear about my comparison choices. Knowing non-primes would not be a valid citeria for comparison based on the fact that this algorithm will short circuit at the first factor it finds, I chose all known primes. This was intentional to make it a fair comparison. To your second point, I only chose a deterministic approach, as it was a sure thing, so that was also intentional. A probabilistic approach might make more sense for massive primes. Thank you for your observations.

jace427

P.S. ..and please excuse my cultural insensitivity. I should have used 0.02 monetary units instead of cents.

[Karel-Lodewijk]

RetardedGenius, on 01 November 2011 - 02:32 PM, said:

You should choose a set range of numbers or a specific number to make the speed comparisons fairer. To simply choose some arbitrary, large number is not enough. After all, any number with a small divisor will be found to be non-prime very quickly; even with a naive implementation.

To be more pedantic still: a distinction should be made between deterministic and probabilistic tests for primality. The fastest deterministic algorithm - that I am aware of - simply divides the number by all of the primes <= the square root of the number being tested; if a prime factor is found the number is non-prime. This algorithm however requires an array of precomputed primes making it unsuitable for applications such as RSA, which utilise massive primes.

Just my £0.02

No there are far better deterministic tests for primality, read http://en.wikipedia....rministic_tests . I'd be very interested if anyone would have a go at one.

Also any deterministic test can be combined with a probabilistic test as in only do the deterministic test if the probabilistic test with very very high probability says the number is probably prime. The probabilistic test aren't probabilistic both ways after all, when my Miller–Rabin says a number is not prime it is a 100% certain of that.

This post has been edited by Karel-Lodewijk: 28 November 2011 - 11:29 AM

[Duckington]

Decided to start learning Ruby a few hours ago, so here's mine finding the prime numbers up to 100:

def isPrime(n)
  for i in 2...n
       return false if (n%i) == 0
  end
  return true
end

(2..100).each { |x| puts x if isPrime(x) }

This post has been edited by Duckington: 08 December 2011 - 03:52 PM

[Karel-Lodewijk]

ryuurei, on 01 July 2011 - 11:01 AM, said:

I suppose I'm rather late to the party here but I've been playing with Ruby a lot lately and thought I'd try my hand at my own sieve of Eratosthenes implementation.

Spoiler

require 'benchmark'

def eratosthenes(to_n)
  list = (2..to_n).to_a
  list.each do |n|
    (n..to_n).each {|x| list.delete(x) if x % n == 0 and x != n }
  end
  return list
end

thousand_sieve = eratosthenes(1000)
benchmark = Benchmark.realtime do
  1.upto(1000) do |n| 
    puts "#{n} is prime." if thousand_sieve.include? n
  end
end
puts "Time = %.5f seconds." %benchmark

It might be a little late but reading this again, I noticed that you did implement a prime generating function but not Sieve of Eratosthenes.

The error is that if you find a prime you do trial division on all future primes. What you should be doing is stepping through your list in steps of the prime found and remove all of those.

@DillonSalsman

Your algorithm is sieve, but the delete in your inner loop really throws the complexity sky-high. Ruby Array is an unsorted container (in your case it is sorted but ruby doesn't know), so delete is an O(n) operation. Ruby arrays are also consecutive in memory so all elements after the delete need to be shifted to the left.

I tried a hand at it myself and came up with this.

require 'mathn'

def sieve_prime(n)
    list = (2..n).to_a
    sqrt_n_index = Math.sqrt(n)-2
    for i in 0 .. sqrt_n_index
        next if (list[i] == nil)
        (i+list[i]).step(n, list[i]) do |j|
            list[j] = nil
        end
    end
    return list.compact
end

I've opted for a lazy approach by not actually truncating the list but setting element to nil.

For example in sieve_prime(10), list starts as

[2,3,4,5,6,7,8,9,10]

Next non-nil element is always prime, so 2 is prime, we step through the list from 2+2 by steps of 2 and make those elements nil

[2,3,nil,5,nil,7,nil,9,nil]

Next non-nil element is always prime, so 3 is prime, we step through the list from 3+3 by steps of 3 and make those elements nil

[2,3,nil,5,nil,7,nil,nil,nil]

The next element 5 is larger than sqrt(10) ~= 3.16, so we are done.

This step might not be immediately obvious from the code because I've taken a slightly different approach. Basically I let the index run from 0..sqrt(10)-2, so 0..1 in this case, notice how list[sqrt(n)-2] initially always contains the last number smaller than sqrt(n)), because sqrt(n) is always rounded down and list[i] initially contains i+2.

Now we return the list without the nils.

This post has been edited by Karel-Lodewijk: 17 December 2011 - 02:46 PM