Algorithms

Notes

Big-O notation with n is the number, while N is the number of bits, so N ~ log(n)

Prime verification

Sieve Function

We store a binary file (should be about 250MB) in the same folder, named primes.dat. If you mess with this, the output will be wrong, and you will receive and email documenting the mistakes. We use a very simple bitset using uint_32's, and the i % 32th bit of bitset[i / 32] tells whether or not i is prime. This is stored in little endian order in the bits in primes.dat. The sieve of Eratosthenes is O(nloglogn) . Memory is O(n)

Search

Quadratics

Doing a search through ranges a, b, and c takes O(abc) assuming random access model.