C 练习实例85

C 语言经典100例

题目：输入一个素数，求最少需要多少个连续的数字 9，才能组成一个可以被该素数整除的正整数。

例如，输入素数 13：

9、99、999、9999、99999 都不能被 13 整除。
999999 可以被 13 整除，因为 999999 ÷ 13 = 76923。

因此，输出结果为 6，表示最少需要 6 个连续的数字 9。

程序分析：

本题的关键是判断由连续数字 9 组成的整数能否被指定素数整除。

最直接的方法是从 9 开始，每次在末尾添加一个 9，依次判断 9、99、999、9999……能否被该素数整除。

但是，随着数字 9 的数量增加，组成的整数会越来越大，容易超出 C 语言整数类型的表示范围。

因此，可以利用取余运算解决这个问题，无需保存完整的整数。

假设当前数字除以素数 p 的余数为 r，那么在末尾添加一个 9 后，新数字的余数为：

r = (r * 10 + 9) % p;

重复计算，直到余数为 0，此时数字 9 的个数就是所求结果。

注意：如果输入的素数为 2 或 5，则不存在符合条件的数字，因为所有由数字 9 组成的正整数，末位都是 9，不可能被 2 或 5 整除。

程序源代码：

实例

#include <stdio.h>

// 判断一个整数是否为素数
int is_prime(int n) {
if (n < 2) {
return 0;
}

for (int i = 2; i <= n / i; i++) {
if (n % i == 0) {
return 0;
}
}

return 1;
}

int main() {
int p;
long long remainder = 0;

printf("请输入一个素数:\n");

if (scanf("%d", &p) != 1) {
printf("输入无效！\n");
return 1;
}

// 验证输入是否为素数
if (!is_prime(p)) {
printf("%d 不是素数！\n", p);
return 1;
}

// 2 和 5 不可能整除只由 9 组成的正整数
if (p == 2 || p == 5) {
printf("不存在能被 %d 整除的连续9组成的数。\n", p);
return 0;
}

// 通过取余法计算，避免大整数溢出
for (int count = 1; count <= p; count++) {
remainder = (remainder * 10 + 9) % p;

if (remainder == 0) {
printf("最少需要 %d 个9组成的数才能被 %d 整除。\n",
count, p);
return 0;
}
}

return 0;
}

以上实例运行输出结果为：

请输入一个素数:
13
最少需要 6 个9组成的数才能被 13 整除。

代码说明：

is_prime()：判断输入的整数是否为素数。
remainder：保存当前由连续数字 9 组成的整数除以 p 的余数。
remainder * 10 + 9：模拟在当前整数末尾添加一个数字 9。
% p：计算余数，避免直接存储不断增大的整数。
remainder == 0：表示当前由连续数字 9 组成的整数可以被 p 整除。
count：记录数字 9 的数量，首次整除时即为最小数量。

算法说明：

对于除 2、5 以外的素数 p，由于 p 与 10 互质，根据数论性质，一定存在一个全部由数字 9 组成的正整数可以被 p 整除，因此循环最多检查 p 次即可找到结果。

该算法不需要保存完整的整数，空间复杂度为 O(1)，查找过程最多执行 O(p) 次取余运算。

提示：本实例只计算所需数字 9 的最少数量，不直接输出由这些数字组成的完整整数，因此即使结果包含大量数字 9，也不会因为构造大整数而发生溢出。

C 语言经典100例

返回顶部

菜鸟教程

C 练习实例85

实例