C 練習例12
問題:101 から 200 の間の素数を判定します。
プログラム分析:素数を判定する方法:ある数をそれぞれ 2 から sqrt(その数) までで割り、割り切れる場合はその数は素数ではなく、割り切れない場合は素数です。
例 1
// Created by www.example.com on 15/11/9.
// Copyright © 2015年 サンプル. All rights reserved.
//
#include <stdio.h>
int main()
{
int i,j;
int count=0;
for (i=101; i<=200; i++)
{
for (j=2; j<i; j++)
{
// j が i で割り切れたらループを抜ける
if (i%j==0)
break;
}
// ループが途中で抜けたかどうかを判定。j<i ならば 2〜j の間に i を割り切れる数があることを示す
if (j>=i)
{
count++;
printf("%d ",i);
// 改行。count でカウントし、5個ごとに改行する
if (count % 5 == 0)
printf("\n");
}
}
return 0;
}
上記の例の出力結果は次のとおりです:
101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199
例
#include <stdio.h>
#include <stdbool.h>
// 関数:数が素数かどうかを判定する
bool isPrime(int num) {
if (num <= 1) return false;
if (num <= 3) return true;
if (num % 2 == 0 || num % 3 == 0) return false;
for (int i = 5; i * i <= num; i += 6) {
if (num % i == 0 || num % (i + 2) == 0) return false;
}
return true;
}
int main() {
printf(101 から 200 の間の素数のリスト:\n");
for (int i = 101; i <= 200; i++) {
if (isPrime(i)) {
printf("%d ", i);
}
}
printf("\n");
return 0;
}
#include <stdbool.h>
// 関数:数が素数かどうかを判定する
bool isPrime(int num) {
if (num <= 1) return false;
if (num <= 3) return true;
if (num % 2 == 0 || num % 3 == 0) return false;
for (int i = 5; i * i <= num; i += 6) {
if (num % i == 0 || num % (i + 2) == 0) return false;
}
return true;
}
int main() {
printf(101 から 200 の間の素数のリスト:\n");
for (int i = 101; i <= 200; i++) {
if (isPrime(i)) {
printf("%d ", i);
}
}
printf("\n");
return 0;
}
コード分析:
isPrime関数:ある数が素数かどうかを判定します。まず明らかに素数でない数を除外し、その後 6k ± 1 の形式を使って残りの可能な因数をチェックし、効率を向上させます。main関数:101 から 200 までのすべての整数を走査し、isPrime関数を使用して各数が素数かどうかをチェックします。もし素数なら、それを出力します。