11
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

C言語で素因数分解

Last updated at Posted at 2019-05-16

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

  1. ユーザから2以上の整数(num)を入力してもらう
  2. 偶数の素数が2のみであることを利用し、numを2で割っていく
  3. 2以外の素数は全て奇数なので、入力された整数を3以上 sqrt(num)(2でnumは奇数となっている)以下の奇数で割る

##割る数が、3以上 sqrt(num) 以下である理由
自然数nが素数でないとき、nの素因数をk (k <= sqrt(n)) とすると、必ず sqrt(n) <= n/k となります(等号成立条件は n=k^2)。割る数と商の大小がnの平方根前後で反転することから、平方根以降の数については約数であるかを調べる必要がないのです。
...うーん、上手く説明できない。

#実装例

soinsu.c
#include <stdio.h>
#include <math.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, cnt = 0;
	printf("%d =", num);
	while (num % 2 == 0){ // 偶数の素数は2のみ
		cnt += 1;
		num /= 2;
	}
	if (cnt > 1)
		printf(" 2^%d *", cnt);
	else if (cnt == 1)
		printf(" 2 *");
	for (i = 3; i <= sqrt(num); i += 2){ // 他の奇数で割っていく
		cnt = 0;
		while (num % i == 0){
			cnt += 1;
			num /= i;
		}
		if (cnt > 1)
			printf(" %d^%d *", i, cnt);
		else if (cnt == 1)
  			printf(" %d *", i);
	}
	// ここまでで num は1または sqrt(num) 以下で最大の素数
	if (num != 1) printf(" %d *", num); // 後者なら追記
	printf("\b \n");
	return 0;
}

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

#実行結果

素因数分解したい整数を入力:90
90 = 2 * 3^2 * 5

素因数分解したい整数を入力:517
517 = 11 * 47
11
3
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
11
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?