CODEWITHSUNDEEP
rubyalgorithmprimessieve-of-eratosthenes
Richard Hamilton
Richard Hamilton

Reputation: 26444

Algorithm - What is wrong with this Sieve of Erastothenes solution

I thought I would create my own implementation of the Sieve algorithm to find prime numbers quicker. Surprisingly, this fails a number of tests.

Here's my algorithm in Ruby for determining if a number is a prime.

def prime?(n)
  primes = [2,3,5,7,9,11,13,17]
  primes.include?(n) || primes.none? { |p| n % p == 0 }
end

How the algorithm works is you take the first couple prime numbers, I took the first 8 to be safe. I would then weed out all the multiples of these prime numbers, as there is no way they could be primes.

Therefore all the other numbers must be prime

I'm shocked to find out my tests fail and I overlooked some numbers. How is this possible? I'm following the algorithm perfectly.

Upvotes: 0

Views: 154

Answers (3)

Abu Hanifa
Abu Hanifa

Reputation: 3057

I'm not very good at ruby but it seems you're not following the algorithm. Also you add 9 as prime number which is not true.

In sieve algorithm at first only need 2 as a prime number.

Pseudocode:

Sieve(n) {
  a[1] := 0                          
  for i := 2 to n do a[i] := 1
  p := 2
  while p2  <  n do {
    j := p2
    while (j  <  n) do {             
      a[j] := 0
      j := j+p
    }
    repeat p := p+1 until a[p] = 1   
  }
  return(a)
}

here A is the array,which's index value indicate the primeness. 0 for not prime, 1 for prime. in while loop mark prime numbers multiple and last pick next prime number in repeat section.

Upvotes: 1

pjs
pjs

Reputation: 19855

To test primality of a given number n you need to check whether it's divisible by any of the primes <= sqrt(n). Since you have hardwired the primes up to 17 into it, your algorithm will only work for values of n <= 172.

On top of that, you included 9 in your list of "primes". This shouldn't affect your test except for the value 9 itself, since anything divisible by 9 is also divisible by 3, but it's quite naughty.

Upvotes: 2

Abhishek Kumar
Abhishek Kumar

Reputation: 169

First of all, you have included 9 in the list of primes. 9 is not a prime number. Try following approach.

  • To find all the primes up to a given number. Start with the smallest prime, 2.
  • Mark 2 as prime, and strike out all the multiples of 2.
  • Next see, which is the smallest number not striked out. It is 3. Print 3 as prime and strike out all the multiples of 3 smaller than n.

  • Then again select the next smallest number not striked out, and so on

    def primeSeive(n)
    while primes[index]**2 <= primes.last
        prime = primes[index]
        primes = primes.select { |x| x == prime || x%prime != 0 }
        index += 1
end

Upvotes: 2

Related Questions