## Prime Numbers: Finding the first N Primes – Part 1 Trivial Approaches

Posted by tekpool on October 2, 2006

**Q: Finding whether or not a number is prime?**

**Sol: **There are several ways to solve this problem. Lets look into some of the more trivial approaches as usual and try to improve on these as we move along.

By Definition, a prime number is a positive integer having exactly one positive divisor other than 1. Therefore the straightforward way to do this will be to check divisibility of the given number starting from 2 to the given number.

There are some easy ways to improve upon this basic approach.

- You do not have to check for all numbers upto n. Some would argue that checking upto n/2 would suffice, since anything greater than this will not divide the given number as a whole number
- Actually, you will not even need to go upto n/2. Checking upto sqrt(n) would suffice. This is because anything if there was a number greater than this that would actuall divide the divide the given number, you would have already visited the factor since that number will be less than or equal to sqrt(n). E.g If 91 was the given number, you would not have to check for numbers greater than 9. This is beacause although 13 divides 91, this would already have been found since you would have checked 7 prior to this and this is less that 9 (floor(sqrt(91))

```
```void GetPrimes(int n)
{
// Start from 3
int j=3;
// There is already one prime (2), so set count=1
int count = 1;
while(count

Advertisements

## logan said

The code is not complete?? Can you please correct this?

Between, this is an excellent site! Great work, God bless you!

## How to Get Six Pack Fast said

My fellow on Orkut shared this link and I’m not dissapointed at all that I came to your blog.

## roddy said

actually if you look it up you only need to check primes up to sqrt(n)

## akanksha said

pls complete this code