Is Prime Number?
I just back from Job Interview in this morning. I was required to write a program to check any number passed is prime number or not. I was not very sure what is prime number, therefore the interviewer asked me to write another program. And, I am able to write it on the spot.
After the interview, I took abit time to search from internet what is prime number and I have written IsPrime() within half an hour. I think I "failed" the test because I shouldn't take that that long time. Anyway, here is the code :
FUNCTION IsPrime(tnNumber AS Integer) AS Boolean
llIsPrime = .T.
*-- Check number from 1 to value of parameter
*-- minus 1 because every number can be
*-- divided without remainer
*-- by itself by default
FOR i = 1 TO tnNumber - 1
IF i = 1
*-- 1 is not prime number
*-- by definition
llIsPrime = .F.
ELSE
*-- If number can be divided
*-- by other number without
*-- remainder,
*-- then it is NOT prime number
llIsPrime = NOT (tnNumber % i = 0)
IF NOT llIsPrime
EXIT
ENDIF
ENDIF
NEXT
RETURN llIsPrime
ENDFUNC
I have tested it, and it should work. Anyone got shorter code for this function?
posted by Chan Kok Kiet (John Jones) @ 4:09 PM
4 comments
4 Comments:
You don't need to go up to the number, only to the number/2. It's not shorter, but it runs twice as fast...
Thank you for your tip. It works. However, can you explain why? Sorry, my mathematical algorithm is not really good. :P
Yes in most cases you can determine if X is a prime by starting from the 'middle' which is X / N (where N is the half of X). For example X is 10. It would sound a little more useless to divide 10 by 9... 8... 7... 6... as it would surely yield remainders. Starting from 10/5 is a good way to start. I think it applies to other numbers as well.
But I'm no too sure... I just woke up and I think I'm still daydreaming... hehe. Anyway have a nice weekend.
To make the code faster (but not smaller), test division by 2, and then by all odd numbers up to the square root of the potential prime.
Explanation: If a number "n" has one factor which is larger than sqrt(n), then it must needs have another factor which is smaller than sqrt(n).
HTH, Hilmar Zonneveld.
Post a Comment
<< Home