Category : OS/2 Files
Archive : EMXTST8F.ZIP
Filename : SIEVE.C
Output of file : SIEVE.C contained in archive : EMXTST8F.ZIP
/* Define BITS to use bit encoding instead of byte encoding */
#include
#include
#include
#define FALSE 0
#define TRUE 1
#define N(x) ((x)/3)
typedef unsigned long ULONG;
typedef unsigned char BYTE;
#if defined (BITS)
#define index(c) ((c)>>3)
#define mask(c) (1<<((c)&0x07))
#define BIT_ON(map,c) (map[index(c)] & mask(c))
#define BIT_OFF(map,c) (!BIT_ON(map,c))
#define SET_TRUE(map,c) map[index(c)] |= mask(c)
#define SET_FALSE(map,c) map[index(c)] &= ~mask(c)
#define BYTES(s) (((s)+7)>>3)
#else
#define BIT_ON(map,c) map[c]
#define BIT_OFF(map,c) !map[c]
#define SET_TRUE(map,c) map[c] = 1
#define SET_FALSE(map,c) map[c] = 0
#define BYTES(s) (s)
#endif
static ULONG isqrt (ULONG x);
static void usage (void);
static ULONG isqrt (ULONG x)
{
ULONG l, r, m;
l = 1; r = x;
while (l < r)
{
m = (l+r) / 2;
if (m > 46340) m = 46340; /* avoid overflow when computing m*m */
if (m*m < x)
l = m+1;
else if (m*m > x)
r = m-1;
else
return (m);
}
return ((l+r)/2);
}
static void usage (void)
{
fputs ("Usage: sieve [-p]
exit (1);
}
int main (int argc, char *argv[])
{
ULONG sqrt_size, i, j, n, primes, size;
int incr, jincr, idx, print_flag;
size_t bytes;
char *p;
BYTE *bitmap;
print_flag = FALSE;
for (idx = 1; idx < argc; ++idx)
if (strcmp (argv[idx], "-p") == 0)
print_flag = TRUE;
else
break;
if (argc - idx != 1)
usage ();
errno = 0;
size = strtoul (argv[idx], &p, 10);
if (errno != 0 || *p != 0 || size < 10 || size > 2000000000)
usage ();
bytes = BYTES (N (size) + 1);
bitmap = malloc (bytes);
if (bitmap == NULL)
{
fputs ("Out of memory\n", stderr);
exit (2);
}
memset (bitmap, 0, bytes);
sqrt_size = isqrt (size);
for (i = 5, incr = 4, n = 1; i <= sqrt_size; i += (incr=6-incr), ++n)
if (BIT_OFF (bitmap, n))
for (j = i, jincr = incr; j <= size/i; j += (jincr = 6-jincr))
SET_TRUE (bitmap, N(i*j));
if (print_flag)
printf ("2 3 ");
for (i = 5, incr = 4, n = 1, primes = 2; i <= size; i += (incr=6-incr), ++n)
if (BIT_OFF (bitmap, n))
{
++primes;
if (print_flag)
printf ("%lu ", i);
}
printf ("\n%lu primes\n", primes);
return (0);
}
Very nice! Thank you for this wonderful archive. I wonder why I found it only now. Long live the BBS file archives!
This is so awesome! 😀 I’d be cool if you could download an entire archive of this at once, though.
But one thing that puzzles me is the “mtswslnkmcjklsdlsbdmMICROSOFT” string. There is an article about it here. It is definitely worth a read: http://www.os2museum.com/wp/mtswslnk/