大整數因子篩選：30 位十進制數對 2~9 取模判斷

問題重述

輸入多個長度 ≤ 30 的非負整數 c（以 -1 結束），對每個 c 輸出所有能整除它的 k（2 ≤ k ≤ 9），無則輸出 none。

關鍵難點：溢出避免

30 位數遠超 64 位整數範圍，必須用**模運算逐位處理**：

對於某 k，維持 rem = (rem * 10 + digit) % k，最終 rem == 0 即可整除。

C++ 實現

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    while (cin >> s && s != "-1") {
        vector ans;
        for (int k = 2; k <= 9; ++k) {
            int rem = 0;
            for (char ch : s)
                rem = (rem * 10 + (ch - '0')) % k;
            if (rem == 0) ans.push_back(k);
        }
        if (ans.empty()) cout << "none";
        else {
            for (size_t i = 0; i < ans.size(); ++i) {
                if (i) cout << ' ';
                cout << ans[i];
            }
        }
        cout << '\n';
    }
    return 0;
}

Java 實現

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String s = sc.next();
            if (s.equals("-1")) break;
            List ans = new ArrayList<>();
            for (int k = 2; k <= 9; ++k) {
                int rem = 0;
                for (char ch : s.toCharArray())
                    rem = (rem * 10 + (ch - '0')) % k;
                if (rem == 0) ans.add(k);
            }
            if (ans.isEmpty()) System.out.println("none");
            else {
                for (int i = 0; i < ans.size(); ++i) {
                    if (i > 0) System.out.print(' ');
                    System.out.print(ans.get(i));
                }
                System.out.println();
            }
        }
    }
}

複雜度

每個數字 O(L × 8)，L ≤ 30，極快。