2 程序的灵魂—算法-2.2 简单算法举例-【例 2.5】
【例 2.5】对一个大于或等于 3 的正整数,判断它是不是一个素数。
算法可表示如下:
S1: 输入 n 的值
S2: i=2
S3: n 被 i 除,得余数 r
S4:如果 r=0,表示 n 能被 i 整除,则打印 n“不是素数”,算法结束;否则执行 S5
S5: i+1→i
S6:如果 i≤n-1,返回 S3;否则打印 n“是素数”;然后算法结束。
改进:
S6:如果i≤ n ,返回S3;否则打印n“是素数”;然后算法结束。
int main() {
int n, i = 2;
printf("请输入一个大于或等于3的正整数: ");
scanf("%d", &n);
// 算法实现
if (n < 3) {
printf("%d 不符合输入要求(应大于或等于3的正整数)。
", n);
} else if (n == 3) {
printf("%d 是素数。
", n);
} else if (n % 2 == 0) {
printf("%d 不是素数。
", n);
} else {
// 从3开始检查到n本身,步长为2,因为偶数已排除
for (; i <= n; i += 2) {
if (n % i == 0) {
printf("%d 不是素数。
", n);
return 0; // 一旦发现有因子,直接结束
}
}
}
printf("%d 是素数。
", n);
return 0;
}