Posted at

C言語で素因数分解

C言語で素因数分解するプログラムを作ってみました。


方法


  1. ユーザから2以上の整数(num)を入力してもらう

  2. 偶数の素数が2のみであることを利用し、numを2で割っていく

  3. 2以外の素数は全て奇数なので、入力された整数を3以上num以下の奇数で割る


実装例


soinsu.c

#include <stdio.h>


int inputNum(void){
int num = 0;
while (1){
printf("素因数分解したい整数を入力:");
scanf("%d", &num);
if (num < 2){
printf("2以上の整数にしてください\n\n");
} else{
break;
}
}
return num;
}

int findFactors(int num){
int i;
printf("%d =", num);
while (num % 2 == 0){ // 偶数の素数は2のみ
printf("2 *");
num /= 2;
}
for (i = 3; i <= num; i++){ // 他の素数で割っていく
while (num % i == 0){
printf("%d *", i);
num /= i;
}
}
printf("%b %n");
return 0;
}

int main(void){
int num;
num = inputNum();
findFactors(num);
return 0;
}



実行結果

素因数分解したい整数を入力:90

90 = 2 * 3 * 3 * 5