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
sofiastrangeAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

a_bCommented:
How are you checking whether the number that he has entered is prime or not?
0
sdstuberCommented:
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
a_bCommented:
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
Bootstrap 4: Exploring New Features

Learn how to use and navigate the new features included in Bootstrap 4, the most popular HTML, CSS, and JavaScript framework for developing responsive, mobile-first websites.

KatanagashiCommented:
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;

Open in new window

0
KatanagashiCommented:
theres a { in my code that it's not needed, sorry
0
a_bCommented:
@Katanagashi: That is a neat optimization you did. Thanks for pointing it out.
0
sdstuberCommented:
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
NovaDenizenCommented:
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
ozoCommented:
> for(int i=3; i<num/2; i=i+2){
#or
 for(int i=3; i*i<=num; i=i+2){
0
thehagmanCommented:
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
sofiastrangeAuthor 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
thehagmanCommented:
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.
How about this:

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;
}

Open in new window

0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
E-Commerce

From novice to tech pro — start learning today.