Oops (Learning from Eratosthenes)

To: debian-devel@lists.debian.org
Subject: Oops (Learning from Eratosthenes)
From: Jonathan Walther <krooger@debian.org>
Date: Tue, 10 Oct 2000 03:22:35 -0700 (PDT)
Message-id: <Pine.LNX.3.96.1001010032203.4215A-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

iQCVAwUBOeLt68K9HT/YfGeBAQH0zQP+JcbyJUJt4m07/zhITsrDaXwI+2wTDFaA
rnRAgUK7dqoTkBXp2MnrpuY1ToJbonstI6zf0KH4R14XGLPltapOKRHKuH9aZMsX
4lHpioKgVVNJxM3XI5Uqgrkklx3E9LeoYjEZML8GAI+UYdER+GcDXXQ0D9GVIBiD
nw+exeu+sCg=
=8nzR
-----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:

Follow-Ups:
- Re: Oops (Learning from Eratosthenes)
  - From: Chad Miller <cmiller@surfsouth.com>

Prev by Date: Oops (Learning from Eratosthenes)
Next by Date: Re: Debian and LDAP?
Previous by thread: Oops (Learning from Eratosthenes)
Next by thread: Re: Oops (Learning from Eratosthenes)
Index(es):
- Date
- Thread