Oops (Learning from Eratosthenes)
- To: debian-devel@lists.debian.org
- Subject: Oops (Learning from Eratosthenes)
- From: Jonathan Walther <djw@lineo.com>
- Date: Tue, 10 Oct 2000 03:21:38 -0700 (PDT)
- Message-id: <Pine.LNX.3.96.1001010031832.4101A-200000@localhost>
-----BEGIN PGP SIGNED MESSAGE-----
The code I included in the previous email was a previous
non-working version; here is an url to the actual code
the compiled, ran, and worked.
http://reactor-core.org/~djw/src/sieve.c
Or else find it attached.
Jonathan
-----BEGIN PGP SIGNATURE-----
Version: 2.6.3ia
Charset: noconv
iQCVAwUBOeLttMK9HT/YfGeBAQFaiQQAjPJ8oc6HXns7OrC7AgQBATUKbeBdvrFY
4FTp6r/8iYsMDxPF8p40+VCSCc/RG7lH+hymect3EbHScHC6KuP7NF5DpOu/pwDA
sBQy3sin7jgAuW2IwG0moB1rZVi2SN7MWbErn8F+zCUToq5nR65/tnLCTes+sj8v
QIzaUDgXwOg=
=5Zr3
-----END PGP SIGNATURE-----
/*
* generate all possible 32 bit primes
* all multiples of 5, 3 and 2 are already excluded
* by using the following bitmask to speed things up.
*/
#include <errno.h>
#include <fcntl.h>
#include <inttypes.h>
#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <sys/mman.h>
#include <sys/types.h>
#include <sys/uio.h>
#include <time.h>
#include <unistd.h>
/* #define MAX 0xFFFFFFFF */
#define MAX 0xFFFFFFFF
typedef unsigned char byte;
void try(int, byte *);
byte *byte2str(byte, byte *);
byte seed[15] = {
0x35, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41
};
byte fa[960] = {
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41,
0x40, 0x14, 0x51, 0x05, 0x04, 0x51, 0x44, 0x14, 0x11, 0x45, 0x10, 0x50, 0x45, 0x14, 0x41
};
byte a1[9], a2[9];
int
main(void)
{
FILE *f;
uint64_t i, j, maxroot;
time_t tm, tn;
byte *map;
try((int)(map = malloc((MAX>>3) + 960)), "malloc");
tm = time(NULL);
printf("Initializing map..");
memcpy(map, seed, 15);
for (i = 15; i < (MAX >> 3); i += 960) {
memcpy(map+i, fa, 960);
}
tn = time(NULL) - tm;
printf(".done %s", ctime(&tn));
maxroot = ceil(sqrt(MAX));
tm = time(NULL);
printf("Seiving primes..");
for (i = 7; i < maxroot; i++) {
if (!(map[i >> 3] & (0x80 >> ((byte)(i & 7)))))
continue;
for (j = (i * i); j < MAX; j += i)
map[j >> 3] &= ~(0x80 >> ((byte)(j&7)));
}
tn = time(NULL) - tm;
printf("..done %s", ctime(&tn));
tm = time(NULL);
printf("Outputting primes to primes.txt ..");
f = fopen("/scratch/krooger/primes.txt", "w");
for (i = 0; i < MAX;) {
for (j = 0; j < 8; j++, i++)
if ((0x80 >> j) & map[i >> 3])
fprintf(f, "%Ld\n", (unsigned long long)i);
}
fclose(f);
tn = time(NULL) - tm;
printf(".done %s", ctime(&tn));
return 0;
}
byte *
byte2str(byte b, byte * s)
{
int i = 8;
while (i--) {
s[i] = b & 1 ? '1' : '0';
b >>= 1;
}
return s;
}
void
try(int expr, byte * msg)
{
if ((expr == -1) || (errno != 0)) {
if (msg == NULL) {
perror("try");
} else {
perror(msg);
}
exit(1);
}
}
Reply to: