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

Well, you may want to buffer the writing to the file in a smarter way, perhaps write to a memory buffer of your own (say 10mb in size) then write that buffer to the file when it's full. Or (suggest) the buffering with setvbuf() or whatever it is.

The same goes for reading, perhaps read a few thousand bytes of the file, parse them and then work out the primes, when you run out, read a few thousand more.

The reason is, file IO is very slow in comparison to memory IO. Also for checking if 'a' is a prime, you only need to test division until sqrt(a) + 1.

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.

Sieve of Eratosthenes - Wikipedia, the free encyclopedia
Watch the animation carefully, then work out why doing i++ is a really bad idea.

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