Return to primes.c CVS log

Up to [CSRG BSD Unix] / 43BSD / games

Annotation of 43BSD/games/primes.c, revision 1.1.1.1

1.1       root        1: /*
                      2:  * Copyright (c) 1980 Regents of the University of California.
                      3:  * All rights reserved.  The Berkeley software License Agreement
                      4:  * specifies the terms and conditions for redistribution.
                      5:  */
                      6: 
                      7: #ifndef lint
                      8: char copyright[] =
                      9: "@(#) Copyright (c) 1980 Regents of the University of California.\n\
                     10:  All rights reserved.\n";
                     11: #endif not lint
                     12: 
                     13: #ifndef lint
                     14: static char sccsid[] = "@(#)primes.c   5.1 (Wollongong) 5/29/85";
                     15: #endif not lint
                     16: 
                     17: /*
                     18:  *     primes [ number ]
                     19:  *
                     20:  *     Print all primes greater than argument (or number read from stdin).
                     21:  *
                     22:  *     A free translation of 'primes.s'
                     23:  *
                     24:  */
                     25: 
                     26: #include <stdio.h>
                     27: #include <math.h>
                     28: 
                     29: #define        TABSIZE 1000            /* size of sieve table */
                     30: #define        BIG     4294967296.     /* largest unsigned int */
                     31: 
                     32: char   table[TABSIZE];         /* table for sieve of Eratosthenes */
                     33: int    tabbits = 8*TABSIZE;    /* number of bits in table */
                     34: 
                     35: float  fstart;
                     36: unsigned       start;                  /* lowest number to test for prime */
                     37: char   bittab[] = {            /* bit positions (to save shifting) */
                     38:        01, 02, 04, 010, 020, 040, 0100, 0200
                     39: };
                     40: 
                     41: unsigned pt[] =        {               /* primes < 100 */
                     42:        2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
                     43:        47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
                     44: };
                     45: 
                     46: unsigned factab[] = {          /* difference between succesive trial factors */
                     47:        10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4,
                     48:        2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4,
                     49:        6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2
                     50: };
                     51: 
                     52: main(argc, argv)
                     53: int    argc;
                     54: char   **argv;
                     55: {
                     56:        register unsigned       *fp;
                     57:        register char   *p;
                     58:        register int    i;
                     59:        unsigned        quot;
                     60:        unsigned        factor, v;
                     61: 
                     62:        if (argc >= 2) {                /* get starting no. from arg */
                     63:                if (sscanf(argv[1], "%f", &fstart) != 1
                     64:                    || fstart < 0.0 || fstart >= BIG) {
                     65:                        ouch();
                     66:                        exit(1);
                     67:                }
                     68:        } else {                        /* get starting no. from stdin */
                     69:                while ((i = scanf("%f", &fstart)) != 1
                     70:                    || fstart < 0.0 || fstart >= BIG) {
                     71:                        if (i == EOF)
                     72:                                exit(1);
                     73:                        ouch();
                     74:                }
                     75:        }
                     76:        start = (unsigned)fstart;
                     77: 
                     78:        /*
                     79:         * Quick list of primes < 100
                     80:         */
                     81:        if (start <= 97) {
                     82:                for (fp = pt; *fp < start; fp++)
                     83:                        ;
                     84:                do
                     85:                        printf("%u\n", *fp);
                     86:                while (++fp < &pt[sizeof(pt) / sizeof(*pt)]);
                     87:                start = 100;
                     88:        }
                     89:        quot = start/2;
                     90:        start = quot * 2 + 1;
                     91: 
                     92: /*
                     93:  * Loop forever:
                     94:  */
                     95:     for (;;) {
                     96:        /*
                     97:         * Generate primes via sieve of Eratosthenes
                     98:         */
                     99:        for (p = table; p < &table[TABSIZE]; p++)       /* clear sieve */
                    100:                *p = '\0';
                    101:        v = (unsigned)sqrt((float)(start + tabbits)); /* highest useful factor */
                    102:        sieve(3);
                    103:        sieve(5);
                    104:        sieve(7);
                    105:        factor = 11;
                    106:        fp = &factab[1];
                    107:        do {
                    108:                sieve(factor);
                    109:                factor += *fp;
                    110:                if (++fp >= &factab[sizeof(factab) / sizeof(*factab)])
                    111:                        fp = factab;
                    112:        } while (factor <= v);
                    113:        /*
                    114:         * Print generated primes
                    115:         */
                    116:        for (i = 0; i < 8*TABSIZE; i += 2) {
                    117:                if ((table[i>>3] & bittab[i&07]) == 0)
                    118:                        printf("%u\n", start);
                    119:                start += 2;
                    120:        }
                    121:     }
                    122: }
                    123: 
                    124: /*
                    125:  * Insert all multiples of given factor into the sieve
                    126:  */
                    127: sieve(factor)
                    128: unsigned factor;
                    129: {
                    130:        register int    i;
                    131:        unsigned        off;
                    132:        unsigned        quot;
                    133: 
                    134:        quot = start / factor;
                    135:        off = (quot * factor) - start;
                    136:        if ((int)off < 0)
                    137:                off += factor;
                    138:        while (off < tabbits ) {
                    139:                i = (int)off;
                    140:                table[i>>3] |= bittab[i&07];
                    141:                off += factor;
                    142:        }
                    143: }
                    144: 
                    145: /*
                    146:  * Error message
                    147:  */
                    148: ouch()
                    149: {
                    150:        fprintf(stderr, "Ouch.\n");
                    151: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.