Trying to create an array with N first primes numbers

Question

I'm pretty new to programming and i'm trying to create a method that returns an array with the N first prime numbers. I know there's a prime class in ruby, but i need to create a method without it.

This what i got so far, but i keep getting weird results. I feel there's a simple logic problem, but i'm failing find it (i don't know exactly how break works in ruby).

Notes:

I'm limiting my first iteration to 2000 to run the tests faster.
@num is the number of primes i have to put in the array_prime

I'm putting 2 since it is the only even prime number so i can step 2 on the second loop

def find_prime_array
  array_prime = [2]
  while array_prime.size <= @num
    isPrime = true
    (1..2000).each do |i|
      (3..(i-1)).step(2) do |j| 
        if i % j == 0
          isPrime = false
          break
        end
      end
      array_prime << i if isPrime
    end
  end
  array_prime
end

Thanks in advance for your help.

score 3 · Accepted Answer · answered Jun 25 '20 at 00:43

It looks like you're trying to implement the Sieve of Eratosthenes, modified to return a certain number of primes rather than check a certain number of candidates, but there's several problems with your approach.

You start with 2 as prime, but start your search at 1. You're going to get 1 and 2 again. Your search should start at 3.

You're correct that you can gain efficiencies by iterating two at a time, but you've left 2 out of your sieve so even numbers remain. Your candidates and your divisors both need to be odds only.

Your check to see if you've matched enough primes is in the outermost loop, so it's never going to stop the inner loop.

@num should be passed in as an argument.

Cleaning that all up, and extracting the inner loop as a function to simplify things...

# Pass in the number of primes to make the function more useful. Default to @num.
def find_prime_array(num_primes = @num)
  # Start with 2 so we only have to check odd numbers.
  array_prime = [2]

  # Step through only the odd numbers.
  (3..2001).step(2) do |i|
    # Extract the prime check into a function.
    array_prime << i if prime?(i)

    # Stop when we have enough primes.
    break if array_prime.size >= num_primes
  end

  array_prime
end

def prime?(i)
  # Also only divide by only the odd numbers.
  (3..(i-1)).step(2) do |j| 
    return false if i % j == 0
  end
  
  return true
end

But we can do this more efficiently. The power of the sieve is you don't have to divide every candidate by every odd number. You only need to divide by the primes you've found so far.

def find_prime_array(num_primes = @num)
  array_prime = [2]

  (3..2001).step(2) do |i|
    array_prime << i if prime?(i, array_prime)

    break if array_prime.size >= num_primes
  end

  array_prime
end

def prime?(i, array_prime)
  array_prime.each do |j| 
    return false if i % j == 0
  end
  
  return true
end

Finally, we can do the same thing more idiomatically with no artificial limit.

def find_prime_array(num_primes)
  primes = [2]

  (3..).step(2) do |candidate|
    if primes.none? { |prime| candidate % prime == 0 }
      primes << candidate
    end
    break if primes.size >= num_primes
  end

  return primes
end

Note that `find_prime_array(2000)` performs 2 million (!) modulo operations. — Stefan, Jun 25 '20 at 07:51
If you're calling modulo anywhere, you're not using the Sieve of Eratosthenes. — Eric Duminil, Jun 25 '20 at 09:08
Here's an example: https://stackoverflow.com/a/432889/6419007 — Eric Duminil, Jun 25 '20 at 09:13
@Stefan I didn't say it's efficient, just that it works. I left the algorithm as is. — Schwern, Jun 25 '20 at 16:44

iAmOren · Answer 2 · 2020-06-25T00:27:31.917

2

Here's my attempt (I don't know ruby...) :

def find_prime_array
  array_prime = [2]
  candidate = 3
  while array_prime.size <= @num
    isPrime = true
    index = 0
    while index<array_prime.size AND array_prime[index] <= squareRoot(candidate) AND isPrime
      if candidate % array_prime[index] == 0
        isPrime = false
        break
      end
      index += 1
    end
    array_prime << candidate if isPrime
    candidate += 2
  end
  array_prime
end

The idea is to check if candidate is divisible by the primes found, and it's redundant to check for divisors bigger than it's square root.
Good job on the increment by 2, as it would be a waste of time to increment by 1!

edited Jun 25 '20 at 00:27

answered Jun 25 '20 at 00:22

iAmOren

2,760
2
11
23

Here are the first 100 primes: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541] – iAmOren Jun 25 '20 at 00:32

Trying to create an array with N first primes numbers

2 Answers2