素数判定と素因数分解
これからは日頃からプログラムを書く癖をつけようと思います.
素数判定
#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; }