• Status: Solved
• Priority: Medium
• Security: Public
• Views: 866

How do i find the nearest prime of a given number?

i am writing a program for the RSA algorithm in C and want to make it more user friendly. the user has to enter two prime numbers. i want to modify it such that, when he enters a wrong prime number, the program automatically selects the next prime number.

For example, if he enters 9, then the program checks 9+1 discovers it is not a prime, then checks 9+1+1 discovers it is a prime amd displays it on the screen
0
sofiastrange
• 3
• 2
• 2
• +4
1 Solution

Commented:
How are you checking whether the number that he has entered is prime or not?
0

Commented:
are you restricting the range of prime inputs?  If so, can you simply pregenerate the primes and save them in an array within your program?

Whether you build in a hard coded list or generate them on the fly it should be pretty trivial to implement.

There are lots of prime number generators you can use.
http://en.wikipedia.org/wiki/Prime_sieve
0

Commented:
In C, this algo will tell you whether the number is prime or not -
int flag = 0;
for(int i=num/2;i<1;i--)
{
if(num%i==0)
{flag = 1; break;}
}
if(flag == 0)
num is the nearest prime

You can keep calling this on each subsequent num till you hit a primer number.
0

Commented:
a_b you made a little mistake on the expression and you can also make it a little faster

if you're using large numbers, every-single second will count
also... using only already found primes for the calculations can make it quicker

you can put the code I've writen and put it in a function, after that you only need to call it

if (num%2==0)
return false;

for(int i=3; i<num/2; i=i+2){
if(num%i==0)
return false;

return true;
0

Commented:
theres a { in my code that it's not needed, sorry
0

Commented:
@Katanagashi: That is a neat optimization you did. Thanks for pointing it out.
0

Commented:
if you're worried about speed, then exhaustive iteration of all odd numbers isn't the way to go.
It is easy to code though.  Using already found primes is effectively building a sieve algorithm as noted above and some sieves are more efficient than others.

There are other direct primality tests too.
Since the task is to both evaluate a number and generate the next prime I don't recommend using the direct tests because you'll have to do the other work anyway.
Unless the user will "likely" enter a prime in which case a fast direct test may be best if you can reasonably assume you won't have to generate the next prime very often and an expected performance lag might be acceptable when it does happen.
0

Commented:
To answer the original question, there is no closed-form expression for finding the next prime.  Instead you just do primality testing on all the subsequent odd numbers.

0

Commented:
> for(int i=3; i<num/2; i=i+2){
#or
for(int i=3; i*i<=num; i=i+2){
0

Commented:
Of course trial division is not an option in determining the next prime if the inputs are big.
Fortunately, your main task is to quickly prove compositeness first for a few - about N/ln(N) - numbers, or even fewer if you at least avoid even numbers and multiples of 3. Usually, only for the first probable primes you need to perform a primality certification algorithm afterwards.
0

Author Commented:
this is what i got so for
the program has to
1. test the input if it is primei
2. display the nearest prime number to a wrong input. for example if 9 is entered by the user, the input is iterated until the next prime number is found.
so 10 is tested, and 11 is tested and diplayed.
// Prime number test
long primzahl (long x)
{
int y = 0, w = 0, i = 2;
//start: //changes!
while (w == 0){
for (i=2;i < x; i++){
if (x%i == 0){
x++;
y = 1;
break;
}
}
w = 1;
}
if (y != 0)      printf("input is not a prime. the next prime  %ld has been selected\n" ,x);
return x;
// Prime number!!
}
0

Commented:
What is your "long"? 32 or 64 bit?
At least for 32 bits, precalculating all primes up to 2^16 with a sieve and then using trial division by these primes *is* feasible.
However, you do trial division on the fly by all numbers from 2 to x -- 2 and all odd numbers from 3 to sqrt(x) would already be a speedup.
BTW
w=0;
while(w==0) {
// something not involving w
w=1;
}
looks a bit obfuscating.

long primzahl(long x) {
long xx = x|1, d; /* Now xx >= x and odd */
if (x<2)
xx = 2;  /* The code below would consider 1 prime (as well as all negatives)! */
else
for (d=3; d*d <= xx; d+=2) if (!(xx%d)) { /* test only small odd divisors */
xx += 2; /* immidiately skip even number */
d = 1; /* restart test divisors */
}
if (xx != x) {
printf("Input %ld is not a prime. ", x);
if (xx > 0)
printf("The next biggest prime %ld has been selected.\n", xx);
else {
x = 17;
printf("The next biggest prime won't fit into data type long. Let's try with %ld, say.\n", xx);
}
}
return xx;
}
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.