3
Contributors
3
Replies
13
Views
3 Years
Discussion Span
Last Post by shubham05
0

We're not going to write it for you.

You should already know that a prime number is a number that is only divisible by 1 and itself.

So, the most trivial way to check if p is prime is to check to make sure it's not divisible by any number from 1 to p. This will work fine.

We can make it faster by considering that if a number is divisible by 2, then it would be disivible by 4, 6, 8, etc, so we only need to check 2 and odd numbers.

We can futher make it faster by considering for each number we check under the square-root, we are also checking the dividand above the square root. Thus, we only need to check numbers from 2 to sqrt(n).

This is probably the fastest you'll get out of a 6 line implementation without getting too fancy.

0

One of the quickest ways is to check if n divided by 2....sqrt(n) results in an even number. If any of them do the number is not prime.
so:
detemine square root of n (rounded up)

loop through 2 to square root of n, dividing n by number. If even division occurs (modulo) n is not prime.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.