help me find a better algorithm for primes

This is a discussion on help me find a better algorithm for primes within the C Programming forums, part of the General Programming Boards category; i need to make a program that finds all primes between some numbers the biggest number is 1000000000. the code ...

  1. #1
    Registered User
    Join Date
    May 2009
    Posts
    17

    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

  2. #2
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    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.

  3. #3
    Registered User
    Join Date
    Jun 2005
    Posts
    6,301
    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.

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,546
    Sieve of Eratosthenes - Wikipedia, the free encyclopedia
    Watch the animation carefully, then work out why doing i++ is a really bad idea.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    Registered User
    Join Date
    May 2009
    Posts
    17
    thank you for you help, this site is awesome all members willing to help

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Find Dialog
    By Lithorien in forum Windows Programming
    Replies: 6
    Last Post: 04-25-2005, 05:28 PM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Q: Recursion to find all paths of a maze
    By reti in forum C Programming
    Replies: 7
    Last Post: 11-26-2002, 08:28 AM
  4. Please review algorithm for filling in quads
    By Shadow12345 in forum C++ Programming
    Replies: 5
    Last Post: 10-17-2002, 04:57 PM
  5. Please review algorithm for filling in quads
    By Shadow12345 in forum Game Programming
    Replies: 1
    Last Post: 10-17-2002, 07:45 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21