## 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