Why Doesnt My Ruby Coding for Finding Prime Numbers Work

Why doesnt my ruby coding for finding prime numbers work?

You have a few problems. One was identified earlier: the location of the statement i = 2. Here is your code with that fixed.

def is_prime?(*nums)
    nums.each do |num|
    i = 2
      while i < num
        if num % i == 0
          puts "#{num} is not a prime"
        else
          puts "#{num} is a prime"
        end
        i += 1
      end
   end
end

When num % i == 0 you've determined the number is not prime, and print a message to that effect, but then you continue checking to see if it is divisible all larger numbers less than num. Each time num % i == 0 you print out that it's not prime. The point is that you don't need to keep checking once you determine a number is not prime.

Another problem is whenever num % i != 0 you print that the number is prime. That's premature, however. You can't draw that conclusion until you determine that num % i != 0 for all integers less than num.

Let's see how to fix these problems. I think the easiest ways is to write a separate method that determines if a single number is prime. I've called that method is_prime? and renamed the main method is_each_prime?.

def is_each_prime?(*nums)
  nums.each { |num|
    puts "#{num} is #{ is_prime?(num) ? '' : "not " }a prime" }
end

def is_prime?(num)
  (2...Math.sqrt(num)).all? { |i| num % i != 0 }
end

puts is_each_prime?(21, 23, 17)
  #=> 21 is not a prime
  #   23 is a prime
  #   17 is a prime

One advantage of creating a separate method is_prime? is that you can test it separately, to make sure it is working properly.

Ruby Prime number program

Let's calculate the square root of 7 (a prime number) and 8 (a composite number):

Math.sqrt(7) #=> 2.6457513110645907
Math.sqrt(8) #=> 2.8284271247461903

This doesn't really help, does it? Apparently, you can't determine if a number is a prime number by calculating its square root.

Instead, you have to check the number's divisors. From Wikipedia:

A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.

Let's determine the divisors of 7: (using the modulo operator %)

7 % 1 #=> 0 <- 7 is divisible by 1
7 % 2 #=> 1
7 % 3 #=> 1
7 % 4 #=> 3
7 % 5 #=> 2
7 % 6 #=> 1
7 % 7 #=> 0 <- 7 is divisible by 7

This satisfies the above definition - 7 is a prime number.

Now, let's determine the divisors of 8:

8 % 1 #=> 0 <- 8 is divisible by 1
8 % 2 #=> 0 <- 8 is divisible by 2
8 % 3 #=> 2
8 % 4 #=> 0 <- 8 is divisible by 4
8 % 5 #=> 3
8 % 6 #=> 2
8 % 7 #=> 1
8 % 8 #=> 0 <- 8 is divisible by 8

8 has two additional divisors 2 and 4. Therefore, 8 is not a prime number.

In Ruby, you could use select to find the divisors:

(1..7).select { |d| 7 % d == 0 } #=> [1, 7]
(1..8).select { |d| 8 % d == 0 } #=> [1, 2, 4, 8]

Finally, here's a variant of your Ruby code that checks if a given number num has exactly two divisors, 1 and num itself:

prime_array = []

(1...100).each do |num|
  if (1..num).select { |d| num % d == 0 } == [1, num]
    prime_array.push(num)
  end
end

prime_array
#=> [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]

The above code can be optimized. I leave that to you.

Ruby - determine if a number is a prime

It's because = is of higher precedence than or. See Ruby's operator precedence table below (highest to lowest precedence):

[ ] [ ]=
**
! ~ + -
* / %
+ -
>> <<
&
^ |
<= < > >=
<=> == === != =~ !~
&&
||
.. ...
? :
= %= { /= -= += |= &= >>= <<= *= &&= ||= **=
defined?
not
or and
if unless while until
begin/end

The problematic line is being parsed as...

(foundDivider = ((n % d) == 0)) or foundDivider

...which is certainly not what you mean. There are two possible solutions:

Force the precedence to be what you really mean...

foundDivider = (((n % d) == 0) or foundDivider)

...or use the || operator instead, which has higher precedence than =:

foundDivider = ((n % d) == 0) || foundDivider

Code Optimization - Generating Prime Numbers

Return true if the number is 2, false if the number is evenly divisible by 2.

Start iterating at 3, instead of 2. Use a step of two.

Iterate up to the square root of the number, instead of the number minus one.

def prime?(number)
  return true if number == 2
  return false if number <= 1 or number % 2 == 0
  (3..Math.sqrt(number)).step(2) do |n|
    return false if number % n == 0
  end
  true
end

This will be much faster, but still not very fast, as @Technation explains.

Here's how to do it using the Sieve of Eratosthenes built into Ruby. You'll need to precompute all the primes up to the maximum maximum, which will be very quick, and then select the primes that fall within each range.

require 'prime'

ranges = Array.new(gets.strip.to_i) do
  min, max = gets.strip.split.map(&:to_i)
  Range.new(min, max)
end

primes = Prime.each(ranges.map(&:max).max, Prime::EratosthenesGenerator.new)

ranges.each do |range|
  primes.each do |prime|
    next if prime < range.min 
    break if prime > range.max
    puts prime
  end

  primes.rewind
  puts "\n"
end

Here's how the various solutions perform with the range 50000 200000:

• Your original prime? function: 1m49.639s
• My modified prime? function: 0m0.687s
• Prime::EratosthenesGenerator: 0m0.221s

The more ranges being processed, the faster the Prime::EratosthenesGenerator method should be.

---

Related Topics