2

I am doing some coding challenges at code wars and ran into this one asking me to make a method that takes a number and determines if it is a prime number or not. If it is prime the method should return "true" if the number is not prime it should return "false".

The method passes every introductory test and each number I can think to throw at it but continually kicks back two tests as incorrect. At this point I'm curious if I am not understanding something about the testing process?

This is my code:

def isPrime(num)  
  counter=2 #is incremented with every time until loop loops
  until counter>999999999999999 do 
    if num.abs <2   
      return false     
    elsif num.abs % counter == 0 && num.abs!=counter  
      return false
    else 
      return true 
    end#if
    counter+=1
  end#
end```

and this is the feed back that code wars is sending back to me

isPrime
Should have isPrime defined.
Test Passed
Should return false for numbers less than 2.
    Test Passed: Value == false
    Test Passed: Value == false
    Test Passed: Value == false
Should return false for non-prime numbers.
    Test Passed: Value == false
    Test Passed: Value == false
    Expected: false, instead got: true    # THESE ARE THE TESTS THAT FAIL
    Expected: false, instead got: true    # THESE ARE THE TESTS THAT FAIL
Should return true for prime numbers.
    Test Passed: Value == true
    Test Passed: Value == true
    Test Passed: Value == true
    Test Passed: Value == true
    Test Passed: Value == true

Also I checked here page for help on the algorithm.

Any help is greatly appreciated.

Community
  • 1
  • 1
SinGar
  • 111
  • 5
  • Unfortunately, I cannot access that page without an account. What value is actually being tested in the two tests that fail? On a general note, using `abs` seems suspect (your program would say -3 is prime, but [negative numbers are (probably) not prime](https://math.stackexchange.com/questions/1002459/do-we-have-negative-prime-numbers)), your algorithm is horribly inefficient as it should only go up to sqrt(num), etc. – Ken Y-N May 11 '16 at 03:03

2 Answers2

2

There are a number of issues here. The biggest is with the if statement you have inside the loop.

if num.abs <2   
    return false     
elsif num.abs % counter == 0 && num.abs!=counter  
    return false
else 
    return true 
end

There is no condition under which this if statement will not terminate the loop and return either true or false in the first iteration. This will prevent counter from ever being incremented.

The next issue is in your loop control. You have

until counter>999999999999999 do

    ...

    counter+=1
end

In this case it would be better to stop at the sqrt(num) rather than some large number. For better performance you probably should instead use as the loop control something like

until counter*counter > num do

This will avoid multiple sqrt calculations. You could precompute the sqrt instead, something like

sqrt_num = num.sqrt
until counter > sqrt_num do

(I don't know Ruby so I may have the syntax wrong, but I think you get the point). If you do this, though, be sure num is not negative before hand.

If you exit from the loop never having found a factor for num you know the number is prime.

andand
  • 17,134
  • 11
  • 53
  • 79
  • Wouldn't calculating `sqrt(num)` once at the head be even more efficient? And stepping by two skipping even numbers (after adding a suitable even check at the head) will make things more efficient still. – Ken Y-N May 11 '16 at 03:11
  • Sure,,, work in progress; the really big problem in his logic is the `if` statement. – andand May 11 '16 at 03:13
0

There are 2 problems in your code

  1. Why are you taking the num.abs? If the tester provides negative numbers, it doesn't fail. By formal definition negative numbers aren't prime.
  2. The program can stop at Math.sqrt(n) https://stackoverflow.com/a/5811176/3804420
Community
  • 1
  • 1
gmuraleekrishna
  • 3,375
  • 1
  • 27
  • 45