Return to nlp.c CVS log

Up to [MW Coherent from dump] / coherent / b / STREAMS / coh.386

Annotation of coherent/b/STREAMS/coh.386/nlp.c, revision 1.1

1.1     ! root        1: /*
        !             2:  * File:       nlp.c
        !             3:  *
        !             4:  * Purpose:    find next lower prime from a number
        !             5:  *             Only use for this module now is calculating NHASH given NBUF.
        !             6:  *
        !             7:  *             Compile -DTEST=1 for test version.
        !             8:  *
        !             9:  * Revised: Wed Aug  4 12:44:29 1993 CDT
        !            10:  */
        !            11: 
        !            12: /*
        !            13:  * ----------------------------------------------------------------------
        !            14:  * Includes.
        !            15:  */
        !            16: #include <common/_tricks.h>
        !            17: #include <common/ccompat.h>
        !            18: #include <common/xdebug.h>
        !            19: 
        !            20: /*
        !            21:  * ----------------------------------------------------------------------
        !            22:  * Definitions.
        !            23:  *     Constants.
        !            24:  *     Macros with argument lists.
        !            25:  *     Typedefs.
        !            26:  *     Enums.
        !            27:  */
        !            28: #if TEST
        !            29: #include <stdio.h>
        !            30: #define TESTPRINT(args)                (printf args)
        !            31: int main  __PROTO((void));
        !            32: #else
        !            33: #define TESTPRINT(args)
        !            34: #endif
        !            35: 
        !            36: /*
        !            37:  * ----------------------------------------------------------------------
        !            38:  * Functions.
        !            39:  *     Import Functions.
        !            40:  *     Export Functions.
        !            41:  *     Local Functions.
        !            42:  */
        !            43: unsigned int           nlp             __PROTO ((unsigned int num));
        !            44: 
        !            45: __LOCAL__ int          isprime         __PROTO ((unsigned int num));
        !            46: __LOCAL__ unsigned int isqrt           __PROTO ((unsigned int num));
        !            47: 
        !            48: /*
        !            49:  * ----------------------------------------------------------------------
        !            50:  * Global Data.
        !            51:  *     Import Variables.
        !            52:  *     Export Variables.
        !            53:  *     Local Variables.
        !            54:  */
        !            55: 
        !            56: /*
        !            57:  * ----------------------------------------------------------------------
        !            58:  * Code.
        !            59:  */
        !            60: 
        !            61: /************************************************************************
        !            62:  * nlp
        !            63:  *
        !            64:  * Return the next prime strictly less than the given argument.
        !            65:  * Return 0 if the argument is 0, 1, or 2.
        !            66:  ***********************************************************************/
        !            67: #if __USE_PROTO__
        !            68: unsigned int nlp (unsigned int num)
        !            69: #else
        !            70: unsigned int
        !            71: nlp (num)
        !            72: unsigned int num;
        !            73: #endif
        !            74: {
        !            75:        unsigned int ret;
        !            76: 
        !            77:        switch(num) {
        !            78:        case 0:
        !            79:        case 1:
        !            80:        case 2:
        !            81:                ret = 0;
        !            82:                break;
        !            83:        default:
        !            84:                for (num--;  num > 2; num--) {
        !            85:                        if (isprime(num)) {
        !            86:                                break;
        !            87:                        }
        !            88:                }
        !            89:                ret = num;
        !            90:        }
        !            91: 
        !            92:        return ret;
        !            93: }
        !            94: 
        !            95: /************************************************************************
        !            96:  * isprime
        !            97:  *
        !            98:  * Return nonzero if the argument is prime, else return 0.
        !            99:  * Return 0 if the argument is 0 or 1.
        !           100:  ***********************************************************************/
        !           101: #if __USE_PROTO__
        !           102: __LOCAL__ int isprime (unsigned int num)
        !           103: #else
        !           104: __LOCAL__ int
        !           105: isprime (num)
        !           106: unsigned int num;
        !           107: #endif
        !           108: {
        !           109:        int ret = 1;
        !           110:        unsigned int nsqrt = isqrt(num);
        !           111:        unsigned int f;
        !           112: 
        !           113:        switch(num) {
        !           114:        case 0:
        !           115:        case 1:
        !           116:                ret = 0;
        !           117:                break;
        !           118:        default:
        !           119:                if ((num & 1) == 0)
        !           120:                        ret = 0;
        !           121:                else for (f = 3;  f <= nsqrt;  f++) {
        !           122:                        if ((num % f) == 0) {
        !           123:                                ret = 0;
        !           124:                                break;
        !           125:                        }
        !           126:                }
        !           127:        }
        !           128: 
        !           129:        TESTPRINT(("isprime(%u) = %d\n", num, ret));
        !           130: 
        !           131:        return ret;
        !           132: }
        !           133: 
        !           134: /************************************************************************
        !           135:  * isqrt
        !           136:  *
        !           137:  * Return the smallet integer greater than or equal to the square root
        !           138:  * of the argument.
        !           139:  ***********************************************************************/
        !           140: #if __USE_PROTO__
        !           141: __LOCAL__ unsigned int isqrt (unsigned int num)
        !           142: #else
        !           143: __LOCAL__ unsigned int
        !           144: isqrt (num)
        !           145: unsigned int num;
        !           146: #endif
        !           147: {
        !           148:        unsigned int ret;
        !           149:        int guess;
        !           150:        int guess2;
        !           151:        int loopct;
        !           152: 
        !           153:        switch(num) {
        !           154:        case 0:
        !           155:        case 1:
        !           156:                loopct = 0;
        !           157:                ret = num;
        !           158:                break;
        !           159:        default:
        !           160:                /* Newton's method, adapted for integers. */
        !           161:                guess = num >> 1;
        !           162: 
        !           163:                /* Use binary to get quick first guess. */
        !           164:                guess = 1 << (__MOST_BIT_UINT(num) / 2);
        !           165: 
        !           166:                for (loopct = 0;  loopct < 32;  loopct++) {
        !           167:                        guess2 = num / guess;
        !           168: 
        !           169:                        TESTPRINT(("g1 = %u  g2 = %u\n", guess, guess2));
        !           170: 
        !           171:                        if (guess >= guess2) {
        !           172:                                ret = guess;
        !           173:                                if (guess - guess2 <= 1) {
        !           174:                                        break;
        !           175:                                }
        !           176:                        } else {
        !           177:                                ret = guess2;
        !           178:                                if (guess2 - guess <= 1) {
        !           179:                                        break;
        !           180:                                }
        !           181:                        }
        !           182:                        guess = (guess2 + guess) / 2;
        !           183:                }
        !           184:                if (ret * ret < num)
        !           185:                        ret++;
        !           186:        }
        !           187: 
        !           188:        TESTPRINT(("isqrt(%d) = %d  loopct = %d\n", num, ret, loopct));
        !           189: 
        !           190:        return ret;
        !           191: }
        !           192: 
        !           193: #if TEST
        !           194: #if __USE_PROTO
        !           195: int main(void)
        !           196: #else
        !           197: int main()
        !           198: #endif
        !           199: {
        !           200:        unsigned int num;
        !           201: 
        !           202:        for (;;) {
        !           203:                printf("enter a number: ");
        !           204:                if (scanf("%u", &num))
        !           205:                        printf("Next lower prime from %u is %u\n",
        !           206:                          num, nlp(num));
        !           207:                else
        !           208:                        break;
        !           209:        }
        !           210: 
        !           211:        return 0;
        !           212: }
        !           213: #endif /* TEST */

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