MAGMA Interview Question Software Engineer / Developers
@blueskin.neo.. about the equation mentioned in your link
(((Any prime is of the form 6*n+k (k=1,5)}}}
what about n=10 & k=5?
Am I understanding it correctly?
dude...it meant any prime can be represented as 6n+1 or 6n-1 and not that any number which has this form is prime.Any way i think he made a mistake saying"So set all 6*n+(1|5) as a prime."
@Sathya: Its said right but the statement was not complete. I changed it. So we basically set all 6*n+(1|5) as a primes and then eliminate their multiples so we should be left with primes in the end. for example: For all primes below 50
set 5,7,11,13,17,19,23,25,29,31,35,37,41,43,47,49
eliminate their multiples. i.e.
-> eliminate multiples of 5: 25,35
-> eliminate multiples of 7: 49
so on... we should be left with primes in the end
@PKT:
No need to traverse until n/2
sqrt(n) will be sufficient
modified code
#include "math.h"
printf("Given number 'n' is ");
for(i=2;i<sqrt(n);i++)
{
if(n%i==0)
{
printf("NOT ");
break;
}
}
printf("a prime number");
Also, don't bother checking even numbers. (ie: check if n is even before starting the loop, then use for(i=3;i<sqrt(n);i+=2) ). This is called the Seive of Erasthones (I think).
www dot optionsbender.com/technologybending/algorithms/primenumbers
- blueskin.neo February 17, 2011