２，３０分プログラミング

後輩が「素因数分解をするプログラムを書け」という課題で困っていたので、

最終的に役立ったのかどうかは分りません。

片手間だったし、後輩も本気ではなかったようなので、コメントはサボりました。

#include <stdio.h>

struct Factor {
    int p;
    int n;
    struct Factor *next;
};

struct Prime {
    int v;
    struct Prime *next;
};

struct PrimeIterator {
    struct Prime *first;
    struct Prime *last;
};

struct PrimeIterator* create_prime_iterator() {
    struct PrimeIterator *it = malloc(sizeof(struct PrimeIterator));
    struct Prime *p = malloc(sizeof(struct Prime));
    p->v = 2;
    p->next = 0;
    it->first = it->last = p;
    return it;
}

int next_prime(struct PrimeIterator *it) {
    int v = it->last->v;
    int next_v = v + 1;
    
    while(1) {
        int divided = 0;
        struct Prime *p;
        for(p = it->first; p != 0; p = p->next) {
            if(next_v % p->v == 0) {
                divided = 1;
                break;
            }
        }
        if(divided) {
            ++next_v;
        } else {
            break;
        }
    }
    
    struct Prime *q = malloc(sizeof(struct Prime));
    q->v = next_v;
    q->next = 0;
    it->last->next = q;
    it->last = q;
    return v;
}

struct Factor* factorization(int m) {
    struct Factor *last = 0, *out=0;
    struct PrimeIterator *it = create_prime_iterator();
    int p = 1;
    
    while(m >= p) {
        p = next_prime(it);
        
        int n = 0;
        while(m % p == 0) {
            m = m / p;
            ++n;
        }
        if(n) {
            struct Factor *f = malloc(sizeof(struct Factor));
            f->p = p;
            f->n = n;
            f->next = 0;
            
            if(last == 0) {
                last = out = f;
            } else {
                last->next = f;
                last = f;
            }
        }
    }
    return out;
}

int main(int argc, char *argv[]) {
    struct Factor *f;
    int n;
    int is_minus;
    if(argc <= 1) {
        printf("please pass positive integer as argument.");
        return 1;
    }
    n = strtol(argv[1], NULL, 10);
    is_minus = (n < 0);
    if(is_minus) {
        n = -n;
    }
    
    f = factorization(n);
    if(is_minus) {
        printf("- ");
    }
    if(f == 0) {
        printf("1");
    } else {
        printf("%d^%d", f->p, f->n);
        f = f->next;
        for(;f!=0;f=f->next) {
            printf(" * %d^%d", f->p, f->n);
        }
    }
    return 0;
}