Need help understanding a line of code

Question

I have been working on prime number programs and I came across some Ruby code:

    (2..prime/2).none?{|i| prime % i == 0}

could someone break this down to me and explain it to me in simple terms. If you are familiar with reddit EIL5. (Explain it Like I'm 5.)

I found the code here:

How can I test if a value is a prime number in Ruby? Both the easy and the hard way?

Answer 1

It's pretty straight-forward even if very inefficient. It breaks down to this:

# For each of the numbers in the range 2 to prime/2...
(2..prime/2).none? do |i|
  # ...test that none of them divide evenly with the given prime.
  # That is the modulus (%) of those two numbers is zero, or no
  # remainder from division.
  prime % i == 0
end

There's better ways of tackling that problem, but this brute-force approach should work.

none? is one of the many convenience methods found in Enumerable. They work on Array and Hash objects, among other things, and provide useful tools for transforming one set of objects into another.

In this case it's testing that none of the numbers meet those criteria. This is the opposite of any? or all? depending on your requirements.

Answer 2

A few notes

Variable name

Naming variables is hard but very important. The code you're showing is, as others have mentionned, to test if a number is prime.

If you're using prime as a variable name for this number, there shouldn't be any use is checking it is prime!

So

(2..prime/2).none?{|i| prime % i == 0}

should be

(2..number/2).none?{|i| number % i == 0}

To make it even more obvious, this code could be written in a method :

def is_prime?(number)
  (2..number/2).none?{|i| number % i == 0}
end

The ? is here to indicate that the method returns a boolean.

For none? :

• none? can be called on any Enumerable (Arrays, Hash and Array-like objects).
• It must be used with a block. It executes this block with every element, one after the other.
• If any block returns a value other than nil or false, none? stops and returns false
• If no block returns a truthy value, it returns true.
• none? is equivalent to all? with the opposite condition in block.

Example :

puts [1, 3, 5, 7].none?{ |n| n.even? }
#=> true
puts [1, 3, 5, 7].all?{ |n| n.odd? }
#=> true
puts [1, 2, 3, 4, 5, 6, 7].none? { |n| n > 6 }
#=> false

Optimization

If number % 2 == 0 is false, it means that number is odd. There's no use in checking if number/2 divides number, we know it is also false.

It means that the range is too big! It could be (2..number/3)

But if number isn't divisible by 3, there's also no point in checking if number is divisible by number/3.

It goes on an on until the range is as small as possible :

(2..Math.sqrt(number))

This will make the execution much faster for big numbers.

Using the method

def is_prime?(number)
  (2..Math.sqrt(number)).none? { |i| number % i == 0 }
end

p (2..100).select { |n| is_prime?(n) }
#=> [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]

To check it is correct, we can use the Prime library :

require 'prime'
p (2..100).select { |n| is_prime?(n) } == Prime.take_while{|p| p<100 }
#=> true

Answer 3

OK, Lucy, I want you to listen closely. If you can understand what I am about to tell you, you can have some ice cream with sprinkles and then go play with your friends.

Yesterday we talked about prime numbers. Do you remember what they are? No, Lucy, not "prime-time" numbers, just "prime" numbers. But you're right, a prime number is a natural number that is 2 or more and is evenly divisible by one, itself and no other number.

Suppose you were given a number and asked to determine if it's prime, that is, if it's a prime number. Let's say the number was 35. How would go about answering the question? That's right, you'd see if it's evenly divisible by any natural number other than 1 and itself. If it was divisible by a number other than 1 and 35 it would not be prime. If it wasn't, it would be prime. Good girl!

OK, is 35 divisible by 2? Yes, that's right, 35 divided by 2 is 17.5, but that's not what I meant. I mean, is it divisible by 2 with no remainder? Remember, if we divide 35 by 2, the remainder is expressed as 35 % 2, which equals 1. So it's not divisible by 2. How about 3? The remainder, 35 % 3, equals 2, so it's not divisible by 3. Nor it it divisible by 4, since 35 % 4 equals 3. Actually, we really didn't have to check if 35 is evenly divisible by 4. Do you know why? Concentrate, Lucy. Don't forget the ice cream with sprinkles. Very good! If it were divisible by 4 it would also be divisible by 2, since 2x2 = 4, but we already found it wasn't divisible by 2.

Is 35 divisible by 5? Yes! You've got it! 5 times 7 is indeed 35, but we could also calculate 35 % 5 = 0, so no remainder. That means 35 is not a prime number. Get it? Yea!

Lucy, I have one more question before you get your ice cream. Suppose the number were 13 instead of 35, and we had found that 13 was not divisible by the numbers 2,3,4,5 and 6. Can you conclude anything from that? Should we next try 7? How bright your are today, Lucy. The number cannot be divisible by any number greater than one-half the number except the number itself. The number divided by any of those numbers will equal zero with a positive remainder. So, we only have to consider if the number is divisible by any number between 2 and one-half of the number.

Good question, Lucy! If the number divided by 2 has a remainder, we just disregard the remainder.

OK, Lucy, you've earned your ice cream so let's go dish it out.