Thread: help me find a better algorithm for primes

i need to make a program that finds all primes between some numbers
the biggest number is 1000000000.

the code that i have works fine, the only problem is that what i thought that would solve this, is too slow

Code:

#include <stdio.h>
int main(){
    FILE *fin=fopen("in.txt","r");
    int t,n1[10],n2[10],i,j,ex,k;
    fscanf(fin,"%d\n",&t);
    for (i=1;i<=t;i++){
         fscanf(fin,"%d %d\n",&n1[i],&n2[i]);
                  }
                  fclose(fin);
                  FILE *fout=fopen("out.txt","w");
for (k=1;k<=t;k++){
    for (i=n1[k];i<=n2[k];i++){
          ex=0;
       for (j=1;j<=i;j++){
           if (i%j==0){
                       ex=ex+1;
                       }
                }
                if (ex==2){
                            fprintf(fout,"%d\n",i);
                           }
                }
     fprintf(fout,"\n");
}
fclose(fout);
    return 0;
}

i want to make it faster, like, 5 secs to find all primes until number 1000000000.

cant think anything right now, well imean a better algorithm, so would appreciate any help provided.

thanks

The first thing you need to do is avoid outputting the values within your loop ..... that is probably the dominant factor slowing down your program. Instead save the values to an array, and then output the array more efficiently. Putting I/O operations into nested loops is a proven technique to slow down those loops, as it forces the program to wait on I/O operations.


Beyond that, you need to improve the efficiency of how you find your primes.

As a starting point, look for information on the Sieve of Eratosthenes.

If that's not fast enough, then look up statistical techniques for proving primality (those are faster for large primes, but there is some likelihood of them giving false positives or false negatives).

A simpler technique would be to compute all the primes up to your maximum value, save them all (in order) to a file or database, and then read the file. Quite practical on any 32 bit system, as your maximum value can be stored in a 32 bit variable.

No guarantee that any of these techniques will succeed within 5 seconds (the speed of all techniques depends on your hardware) but I'll bet any of these will be more effective than the technique you're using.

thank you for you help, this site is awesome all members willing to help