Research In Motion Interview Question
Software Engineer in Testsno that is wrong.. with the check of 6k, you're considering only divisibility by 2 and 3. what about those that are divisible by other primes. for eg: consider 25 = 6(4)+1, holds true for your check. but it is not prime.
1. Every composite number can be represented uniquely as multiple of Prime Numbers.
2. Since every prime number must in in the form of 6k+1 or 6k-1, just try to divide 4 <= x <= sqrt(num).
Where x is in the form of 6k+(-)1
- DD March 30, 2010