Next Prime

Write a function (in whatever language you want) to find the next prime number after a given number.

C++:
01 bool isPrime(int x)
02 {
03     for(int i=2;i<x;i++){
04         if((x%i)==0)
05             return false;
06     }
07     if(x==1)
08         return false;
09     return true;
10 }
11 int nextPrime(int x)
12 {
13     while(true){
14         x++;
15         if(isPrime(x))
16             return x;
17     }
18 
19 }

A better solution(Post by Ming Zhang):

The simplest method was developed by Eratosthenes in the 3rd century B.C. Here’s how it works: Suppose we want to find all the prime numbers between 1 and 64. We write out a table of these numbers, and proceed as follows. 2 is the first integer greater than 1, so it is obviously prime number. We now cross out all multiples of two. The next number that we haven’t crossed out is 3. We circle it and cross out all its multiples. The next non-crossed-out number is 5, so we circle it and cross out all its multiples. We only have to do this for all numbers less than the square root of our upper limit (in this case sqrt(64)=8) since any composite number in the table must have at least one factor less than the square root of the upper limit. What’s left after this process of elimination is all the prime numbers between 1 and 64.
So if N is the given number, check between 1 and 2*N.

Advertisements
This entry was posted in Number trick. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s