• C

Prime Number Conundrum...

I am trying to write a program that will allow input of two numbers (min and max) and then determine all of the prime numbers between the two numbers.

I can not figure out how to do this...

I know what prime numbers are but I can not figure out a quick way to implement this with code... I was thinking about using the % to see if there was a remainder but I could not figure out how to go about it...

Any help?


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.

mapperAuthor Commented:
Edited text of question.
There is no "shortcut" algorithm for determining whether a number is prime. That is one of reasons for the continuing interest in prime numbers. Straightforward algorithms all involve dividing each candidate number (say n) by numbers from 2 to n/2. This can be approached a number of ways. There may be shortcuts, but only in cases that fulfill specific conditions.

The general case is not hard to program. It could take a lot of computing time, but that depends on the size of numbers being considered.


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
mapperAuthor Commented:

I know I only need to be concerned with numbers up to the sqrt of the max value, but the logic to implementing it is what causes me confusion - I am new to C and I get confused easily when confronted with figuring out and then implementing the logic behind the code...

I will test to make sure that the min is > 1 and the max is > min - this will let me know that I have a valid set of numbers (2 to 20 ) - then I know that basically it's all odds except those divisible by 5 -- So, I will need a while to make sure scanf is returning only 2 numbers - then determine the min and max values are valid - then do I start dividing by the min into the min using the modulus?  This is where I am getting foggy...


Sure. A basic test would look like:

testing numbers m through n:

int prime;

for(i=m; i<=n; ++i)
{   prime=1;   /* assert i is prime */
    for(j=2; j<=i/2; ++j)
    {   if(i%j==0)prime=0;
    }  /* if i is divisible by j it is */
       /* evidently not prime           */

    if(prime)printf("%d is prime\n",i);

You can, of course, as you have pointed out, optimize this by various means: check j only up to the square root of i. Only check the odd numbers between m and n (be careful not to exclude 2 though!). Only check odd numbers that don't end in 5. etc. etc.
mapperAuthor Commented:

Thanks! Once again the anxiety brought about by learning something new has blinded me to the obvious!  I wish I could learn to have more faith in my abilities...  

Thanks again,  I appreciate the nudge...

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

From novice to tech pro — start learning today.