C語言練習實例85：判斷素數能整除多少個9組成的數

本實例輸入一個素數 p，尋找最小的由全 9 組成的數（如 9、99、999...）使其能被 p 整除，輸出 9 的個數及該數值。

程序分析

• 從 sum = 9 開始，每次循環 sum = sum * 10 + 9 生成下一個全 9 數。
• 判斷 sum % p == 0，滿足則跳出，輸出計數 i 和 sum。
• 利用 long int 儲存較大數值。

源代碼

// Created by www.runoob.com on 15/11/9.
// Copyright © 2015年 菜鳥教程. All rights reserved.
//
#include <stdio.h>
#include <stdlib.h>

int main() {
    int p, i;
    long int sum = 9;

    printf("請輸入一個素數:\n");
    scanf("%d", &p);

    for (i = 1;; i++)
        if (sum % p == 0)
            break;
        else
            sum = sum * 10 + 9;

    printf("素數%d能整除%d個9組成的數%ld\n", p, i, sum);
    return 0;
}

運行示例

請輸入一個素數:
13
素數13能整除6個9組成的數999999

數學背景

這與費馬小定理相關：對於不整除 10 的素數 p，存在最小正整數 k 使得 10^k ≡ 1 (mod p)，此時 (10^k - 1)/9 即為由 k 個 9 組成的數，能被 p 整除。