素数判定と素因数分解

これからは日頃からプログラムを書く癖をつけようと思います.

素数判定

#include <stdio.h>

int isPrime(int n) {
    int i;

    if( n < 2 ) return 0;
    if( n == 2 ) return 1;
    if( n % 2 == 0 ) return 0;

    for( i = 3; i * i <= n; i += 2 ) {
        if( n % i == 0 ) return 0;
    }

    return 1;
}

int main(void) {
    int n;

    for( n = 1; n <= 100; n++ ) {
        printf("%3d", n);
        if( isPrime(n) ) {
            printf("(素数)\n");
        } else {
            printf("(非素数)\n");
        }
    }

    return 0;
}

素因数分解

"16"と入力した場合,"2*2*2*2"のように出力されます.

#include <stdio.h>
#include <stdlib.h>

int isPrime(int n) {
    int i;

    if( n < 2 ) return 0;
    if( n == 2 ) return 1;
    if( n % 2 == 0 ) return 0;

    for( i = 3; i * i <= n; i += 2 ) {
        if( n % i == 0 ) return 0;
    }

    return 1;
}

int main(void) {
    int *primeList;
    int n;
    int flag = 0;
    int i, idx;

    printf(">");
    scanf("%d", &n);
    if( n == 1 ) {
        printf("%d\n", n);
        return 0;
    }

    primeList = malloc(sizeof(int) * n);

    primeList[0] = 2;
    idx = 1;
    for( i = 3; i <= n; i += 2 ) {
        if( isPrime(i) ) {
            primeList[idx++] = i;
        }
    }

    for( idx = 0; primeList[idx] <= n; ) {
        if( n % primeList[idx] == 0 ) {
            if( !flag ) {
                printf("%d", primeList[idx]);
                flag = 1;
            } else {
                printf("*%d", primeList[idx]);
            }
            n /= primeList[idx];
        } else {
            idx++;
        }
    }

    free(primeList);

    return 0;
}