はじめに
この実験では、C プログラムを使用して整数を素因数に分解する方法を学びます。この実験では以下の手順がカバーされます。
- ユーザーから整数の入力を読み取る。
- 入力された数を素数で割り、完全に因数分解されるまで続けるアルゴリズムを実装する。
- 入力された数の素因数を出力する。
この実験が終わるころには、整数、素数、および C 言語の基本的なプログラミング概念をより深く理解することができるようになります。
C 言語で整数を素因数分解する
整数の読み取り
このステップでは、素因数分解のために C プログラムでユーザーから整数の入力を読み取る方法を学びます。ユーザーに数値の入力を促し、それをさらなる処理のために保存する単純なプログラムを作成します。
まず、~/project ディレクトリに新しい C ファイルを作成しましょう。
cd ~/project
nano prime_factorization.c次に、整数を読み取るための以下のコードを追加します。
#include <stdio.h>
int main() {
int number;
printf("Enter a positive integer to factorize: ");
scanf("%d", &number);
printf("You entered: %d\n", number);
return 0;
}コードを分解してみましょう。
#include <stdio.h>は標準入出力ライブラリをインクルードします。int main()はプログラムの実行が始まるメイン関数です。printf()はユーザーにプロンプトを表示するために使用されます。scanf()はユーザーからの整数入力を読み取ります。%dは整数の書式指定子です。&numberはnumber変数のメモリアドレスを渡します。
プログラムをコンパイルして実行しましょう。
gcc prime_factorization.c -o prime_factorization
./prime_factorization出力例：
Enter a positive integer to factorize: 24
You entered: 24完全に因数分解されるまで素数で割る
このステップでは、前のプログラムを修正して素因数分解アルゴリズムを実装します。prime_factorization.c ファイルを更新して、入力された数を素数で割り、完全に因数分解されるまで続けます。
既存のファイルを開きます。
cd ~/project
nano prime_factorization.c前のコードを以下の実装に置き換えます。
#include <stdio.h>
void factorize(int number) {
printf("Prime factors of %d: ", number);
// Start with the smallest prime number
for (int divisor = 2; divisor <= number; divisor++) {
while (number % divisor == 0) {
printf("%d ", divisor);
number /= divisor;
}
}
printf("\n");
}
int main() {
int number;
printf("Enter a positive integer to factorize: ");
scanf("%d", &number);
// Check for valid input
if (number <= 1) {
printf("Please enter a number greater than 1.\n");
return 1;
}
factorize(number);
return 0;
}素因数分解アルゴリズムを分解してみましょう。
factorize()関数が素因数分解のプロセスを処理します。- 最小の素数 (2) から始めます。
- 外側の
forループは各潜在的な除数を試します。 - 内側の
whileループは現在の除数で数を繰り返し割ります。 - 見つかった素因数をその都度出力します。
- 各反復で整数除算によって数を更新します。
プログラムをコンパイルして実行します。
gcc prime_factorization.c -o prime_factorization
./prime_factorization出力例：
Enter a positive integer to factorize: 24
Prime factors of 24: 2 2 2 3
Enter a positive integer to factorize: 100
Prime factors of 100: 2 2 5 5素因数の出力
このステップでは、素因数分解プログラムを拡張して、素因数のより詳細で整形された出力を提供します。既存の prime_factorization.c ファイルを修正して、結果の表示を改善します。
ファイルを開きます。
cd ~/project
nano prime_factorization.c改良された因数分解関数でコードを更新します。
#include <stdio.h>
void factorize(int number) {
int original_number = number;
int factor_count = 0;
printf("Prime Factorization of %d:\n", original_number);
printf("---------------------\n");
// Start with the smallest prime number
for (int divisor = 2; divisor <= number; divisor++) {
int current_factor_count = 0;
while (number % divisor == 0) {
number /= divisor;
current_factor_count++;
factor_count++;
}
// Print factors with their exponents
if (current_factor_count > 0) {
printf("%d^%d ", divisor, current_factor_count);
}
}
printf("\n\nTotal number of prime factors: %d\n", factor_count);
}
int main() {
int number;
printf("Enter a positive integer to factorize: ");
scanf("%d", &number);
// Check for valid input
if (number <= 1) {
printf("Please enter a number greater than 1.\n");
return 1;
}
factorize(number);
return 0;
}このバージョンの主な改良点：
- 素因数を表示するための整形を追加
- 各素因数の指数を表示
- 素因数の総数をカウント
- 表示用に元の入力数を保持
プログラムをコンパイルして実行します。
gcc prime_factorization.c -o prime_factorization
./prime_factorization出力例：
Enter a positive integer to factorize: 24
Prime Factorization of 24:
---------------------
2^3 3^1
Total number of prime factors: 4
Enter a positive integer to factorize: 100
Prime Factorization of 100:
---------------------
2^2 5^2
Total number of prime factors: 4まとめ
この実験では、ユーザーから整数の入力を読み取り、素因数分解アルゴリズムを実装し、与えられた数の素因数を出力する方法を学びます。主な手順には、整数の読み取り、数を素数で割って完全に因数分解すること、および素因数の出力が含まれます。
プログラムはまず、ユーザーに正の整数の入力を促し、それを変数に格納します。素因数分解アルゴリズムは factorize() 関数で実装され、入力された数は完全に因数分解されるまで素数で割られます。その後、素因数がコンソールに出力されます。
