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.

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

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

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with Premium.
Start your 7-day free trial.

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.

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

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.

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

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.

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.

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!!

}

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

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
E-Commerce

From novice to tech pro — start learning today.

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with Premium.
Start your 7-day free trial.