Link to home
Start Free TrialLog in
Avatar of mapper
mapper

asked on

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?

Thanks,

Mapper
Avatar of mapper
mapper

ASKER

Edited text of question.
ASKER CERTIFIED SOLUTION
Avatar of imladris
imladris
Flag of Canada image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of mapper

ASKER

imladris,

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

Thanks,

Mapper
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.
Avatar of mapper

ASKER

Imladris,

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

Mapper