Finding prime numbers in a range

Question

Finding the prime numbers between two given integers in the minimum number of comparisons:

#include <stdio.h>
#include <conio.h>
#include <math.h>
void main()
{
 clrscr();
 int i,n,count,n1,n2;
 printf("Enter n1 and n2:");
 scanf("%d",&n1);
 scanf("%d",&n2);
 n=n1;
 int c=0; //variable to store number of comparisions (number of times while() runs)
 for(n=n1;n<=n2;n1++,n=n1)
 {
 count=0; //number of factors found
 i=2;
 while((n>0)&&(i<=sqrt(n))) //condition for minimum comparisions
 {
 printf("\n\t%d",c++);//printing the comparision number
 if(n%i==0)
 {
 count++;
 n/=i;
 }
 else i++;
 }
 if(count==0)
 printf("\n%d",n1);
 }
 getch();
}

Answer 1

I have found some things that might help you improve your code:

Strive for portable code

Several of the features of this code are either platform-specific or compiler-specific or both. Specifically, #include <conio.h>, clrscr(), and getch() are all non-standard. Instead consider portable replacements. For instance you could use this instead of clrscr():

putchar('\f');

Or possibly this:

for (int lines=40; lines; --lines)
 putchar('\n');

Alternatively, one could eliminate it entirely, which is what I've done in my modified version of your code.

Follow standard declaration of main

Your compiler may allow you to declare void main() but that construction is technically only valid for what are called "non-hosted" environments, e.g. one in which you are not running Windows. For that reason, you should use the standard int main() instead. Note that you don't need to explicitly provide a return 0; at the end of main -- it's created implicitly by the compiler.

Whitespace improves readability

Allofyourwordsarecrammedtogether. Inserting some spaces in your lines will make them much easier to read. For example, instead of this:

while((n>0)&&(i<=sqrt(n)))

try this:

while((n > 0) && (i <= sqrt(n)))

Avoid scanf if you can

There are so many well known problems with scanf that you're usually better off avoiding it. The usual approach is to read in user input into a string and then parse from there, in this case using something like atoi().

Eliminate redundant code

In this case, the line n=n1; is redundant since the initializer of the for loop does that again just two lines later.

Consider reducing the scope of variables

The variable n is only used within the for loop, so you could declare it within the initializer:

for(int n=n1; n <= n2; n1++, n=n1)

Use a for loop instead of while

Because the i variable is used only within the while loop, consider again reducing scope and turning that into a for loop:

for (int i=2;(n>0) && (i <= sqrt(n)); ) 

Even better, in that loop, the only use of n is for testing primes, so within it you can instead use a variable local to that loop. I've used t (for testing):

for (int i=2, t=n; (t>0) && (i <= sqrt(t)); ) 
{
 printf("\t%d\n",c++);//printing the comparision number
 if(t%i==0)
 {
 count++;
 t/=i;
 }
 else i++;
}

This change also allows you to remove n1 entirely and to simply use n everywhere that n1 had been used.

Improve your algorithm

Except for 2, all prime numbers are odd. You can take advantage of that to reduce the number of comparisons:

for (int i=2, t=n; (t>0) && (i <= sqrt(t)); ) 
{
 printf("\t%d\n",c++);//printing the comparision number
 if(t%i==0)
 {
 count++;
 t/=i; // better: break;
 }
 else if (i==2) 
 {
 ++i;
 } else 
 {
 i += 2;
 }
}

However, once we discover that a number is not prime, why continue factoring it? You can eliminate even more comparisons by replacing the line t/=i with break to break out of the enclosing for loop.

You can do a similar optimization on the outer loop, incrementing it by 2 each loop iteration once you assure that it is odd coming into the loop.

Print newlines after rather than before

The code currently has printf("\n%d", n1); but the effect is that the last line printed doesn't actually end with \n. Instead, re-arrange the two printf statements to that they both end rather than begin with \n.

Results:

When I applied all of these to your code, I found that when I compute the primes from 500 to 1000, the original code made 6766 comparisons, while the optimized version made 1444.

• rolfl: for (int lines=40; lines; --lines) putchar('\n'); really? Otherwise +1
• Edward: @rolfl: hold on, I have to reload the paper roll in my TTY...
• Ashhar Hasan: Thanks a lot. I never really pondered enough to notice that all primes except two are odd. About scanf, do you mean to say that I should use something like gets() to read in the input as a string and then process it? And do for loops and while loops have any major difference in functionality that I should know of? WHITESPACES.
• Ashhar Hasan: Also how exactly does atoi() function. Suppose I have a string like [1,2,+,3,-,4,5]. How does atoi() process the string? (PS: I actually need this for another one of my programs.)
• Edward: I mean that you could use getline to fetch an entire line, and then use atoi to pull out an integer. However if you feed it a string like [1,2,+,3,-,4,5] it will simply return '0'.

Answer 2

Edward seemed to do a good job improving your code with your method of finding primes by checking divisibility by repeatedly dividing.

However, if your task is to quickly generate a list of primes in a large range, using a prime number sieve (e.g., Sieve of Eratosthenes or an optimized version like Sieve of Atkin or wheel sieves) is a better method.

Your method (as well as Edward's improvement by reducing redundant factors) takes \$O(N^{1.5})\$ to generate a list of primes from 1 to \$N\$ (\$\Sigma_{k=1}^{N} \sqrt{k} \sim O(N^{1.5}) \$). The Sieve of Eratosthenes takes \$O(N)\$ time to generate the primes from 1 to \$N\$ and the optimized variations are asymptotically faster and can take \$O(N/\log \log N)\,ドル though you should note for \$N = 2^{32} \sim 4 \;{\rm billion}\$ (common maximum value for an unsigned int), \$\log \log N = 5\$ and for \$N = 2^{64} \sim 10^{19}\$(common maximum value of an unsigned long long int), \$\log \log N = 6\$).

If you need to find larger primes (for example doing RSA and requiring 512-bit primes) or primes in a very small range, its probably better by first checking divisibility against a list of small primes (first 1000 primes or so) and then switch to a probabilistic primality test like Miller-Rabin or Baillie-PSW.

• Ashhar Hasan: I'll leave that for my final year of studies. Really not comfortable with standard algorithms. But thanks anyway.