| 
  • Earn a $50 Amazon gift card for testing a new product from the makers of PBworks. Click here to apply.

  • If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.

View
 

PrimeStream

Page history last edited by Kenneth Finnegan 11 years, 4 months ago

Prime Stream is designed to generate 64 bit prime numbers as quickly as possible to help factor large numbers.  I originally wrote this code to help me solve Project Euler problem #3.  One thing to note about it is that when it is initialized, it generates another thread to generate the prime numbers and store in the buffer, so this code will take advantage of multicore systems.

 

Code:

 primestream.c (version 0.3)

 

Usage:

#include <stdio.h>

#include "primestream.c"

main() {

     primestream *foo = ps_init();

     while(1) {

          printf("%llu\n", ps_getprime(foo)); // %llu is unsigned long long, uint64_t

     }

}

 

Theory:

The basic theory behind this code is that if a number isn't prime, it must be divisible by a smaller prime number.  Thus, there's no need to check to see if a number is divisible by nonprimes since they're a multiple of a prime.

The second shortcut uses the square root of the number being checked.  If you haven't found a factor of a number by the time you've reached the square root, it doesn't exist because you'd have found the corresponding factor by then.  ie 2 * 8 = 16, but by the time you're checking 8, you'd have already passed 2.  Note that in the actual code (ps_isprime(ps_listnode *node, uint64_t num)) it squares the prime currently being checked instead of calculating the square root of num.

 


Extensions:

There still needs to be a way to stop the extra thread and free all the resources if the prime generator is no longer needed. 

 

The use of a linked list to store the known prime numbers may not be optimal, but is good enough for me.

 

NOTE: Patches are perfectly welcome!  Contact us.


Sources:

Project Euler

Wikipedia

Prime Sieve

Comments (0)

You don't have permission to comment on this page.