Skip to content

Instantly share code, notes, and snippets.

@mxswd
Created June 24, 2011 03:26
Show Gist options
  • Save mxswd/1044166 to your computer and use it in GitHub Desktop.
Save mxswd/1044166 to your computer and use it in GitHub Desktop.
Prime number generator. First 5gb's worth.
/* This code is in public domain. Use for whatever purpose at your own risk. */
#include <stdio.h>
#include <string.h>
#include <stdint.h>
#define MAXN 10000000000ll /* maximum value of N */
#define P1 156250100ll /* = ceil(MAXN/64) */
#define P2 5000000000ll /* = ceil(MAXN/2) */
#define P3 50000ll /* = ceil(ceil(sqrt(MAXN))/2) */
uint64_t sieve[P1];
#define GET(b) ((sieve[(b)>>5ll]>>((b)&31ll))&1ll)
void make()
{
uint64_t i, j, k;
memset(sieve, 0ll, sizeof(sieve));
printf("Mems have been allocated\n");
for (k = 1ll; k <= P3; k++) {
if (GET(k)==0ll) {
for(j=2ll*k+1ll, i=2ll*k*(k+1ll); i<P2; i+=j) {
sieve[i>>5ll]|=1ll<<(i&31ll);
}
}
if (k % 1000ll == 0) {
printf("%lu / %d\n", k, P3);
}
}
}
int isprime(uint64_t p) { return p==2ll || (p>2ll && (p&1ll)==1ll && (GET((p-1ll)>>1ll)==0ll)); }
int main(void)
{
printf("%ld ", MAXN);
printf("%ld ", P1);
printf("%ld ", P2);
printf("%ld ", P3);
uint64_t i, n;
FILE *file = fopen("tehprimes", "w");
uint64_t total = 0ll;
uint64_t logval, idown;
make();
printf("OMG Start\n");
for (n = 0ll, i = 0ll; i <= MAXN; i++) {
if (isprime(i)) {
logval = 2ll;
idown = i;
fprintf(file, "%d\n", i);
while (idown > 10ll) {
logval++;
idown /= 10ll;
}
total += logval;
n++;
if (n % 5000000ll == 0ll) {
printf("%ld / 100\n", n/5000000l);
}
}
}
printf("The number of primes below 10^ is %llu.\nFile size in bytes: %llu\nDon't push anything, just close window", n, total);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment