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
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
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
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
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.
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.
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
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
ASKER