• 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

last edited by 13 years 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.

### 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.

Project Euler

Wikipedia

Prime Sieve