Factor_m30 - 自然数の素因数分解
English English edition is here.

プログラムリスト

Factor_m30 - Rev.1.00 : Dec. 9, 2012
#include <stdio.h>
#include <stdlib.h>

int
_sqrt(a)
    int a;
{
    int x, t, s, scale;

    x = a;
    if (x > 0) {
        scale = 0;
        if (x < 0x8000) { x <<= 16; scale = 8; a = x; }
        x >>= 8;
        s = 8;
        for (t = 0x400000L; x < t; t >>= 2) s--;
        t = 88;
        t <<= s; x *= 22; s += 5;
        x >>= s; s = a;
        t += x;  x = s;
        s /= t;
        s += t;
        s >>= 1; t = x;
        x /= s;
        x += s;
        x >>= 1; s = x;
        s++;
        s *= x;
        if (t > s) x++;
        if (scale) { x += 127; x >>= 8; }
    }
    return x;
}

int
print_factor(n)
    int n;
{
    int b, c, p;

    printf("%d:", n);
    if (n <= 1) {
        printf(" %d\n", n);
    }else {
        b = _sqrt(n);
        c = n;
        /* 2, 3, 5, 7 */
        p =  2; while(c % p == 0) { c /= p; printf(" %d", p); }
        p += 1; while(c % p == 0) { c /= p; printf(" %d", p); }
        p += 2; while(c % p == 0) { c /= p; printf(" %d", p); }
        p += 2; while(c % p == 0) { c /= p; printf(" %d", p); }
        if (c != 1) {
            do {
                /* mod 30 */
                p += 4; while(c % p == 0) { c /= p; printf(" %d", p); }
                p += 2; while(c % p == 0) { c /= p; printf(" %d", p); }
                p += 4; while(c % p == 0) { c /= p; printf(" %d", p); }
                p += 2; while(c % p == 0) { c /= p; printf(" %d", p); }
                p += 4; while(c % p == 0) { c /= p; printf(" %d", p); }
                p += 6; while(c % p == 0) { c /= p; printf(" %d", p); }
                p += 2; while(c % p == 0) { c /= p; printf(" %d", p); }
                p += 6; while(c % p == 0) { c /= p; printf(" %d", p); }
            } while ((p < b) || (c != 1));
        }
        if (c != 1) printf(" %d", c);
        printf("\n");
    }
    return n == c ? 1 : 0;
}

int
main(argc, argv)
    int     argc;
    char   *argv[];
{
    int a;

    if (argc >= 2) {
        for (a = 1; a < argc; a++)
            print_factor(abs(atoi(argv[a])));
    } else {
        printf("usage: factor [number ...]\n");
    }
    return 0;
}

バグ

このプログラムは下記の電卓用プログラムで使われているアルゴリズムをCで説明するためのものです。
大きな整数を素因数分解する実用アプリケーションとして使われることを意図していません。

SEE ALSO

factr - integer factorization program for the HP-42S
factr - integer factorization program for the HP 15C
Algorithms for integer square root and hypot (JAPAN in Japanese)

www.finetune.co.jp [Mail] © 2000 Takayuki HOSODA.
Powered by
 Finetune