CODEWITHSUNDEEP
arraysrubyprimesbreak
Ale
Ale

Reputation: 93

Trying to create an array with N first primes numbers

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:

Thanks in advance for your help.

Upvotes: 1

Views: 164

Answers (2)

Schwern
Schwern

Reputation: 165165

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

Upvotes: 3

iAmOren
iAmOren

Reputation: 2804

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!

Upvotes: 2

Related Questions