Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [C] Hàm isSquareFree — số không chia hết cho bình phương nguyên tố

    Một số nguyên dương n được gọi là square-free nếu không tồn tại số nguyên tố p sao cho p² chia hết n (tức trong phân tích thừa số nguyên tố, mọi mũ đều bằng 1). Viết hàm int isSquareFree(int n) trả về 1 nếu đúng.

    Ví dụ: 30 = 2·3·5 → square-free; 12 = 2²·3 → không.

    Ngữ cảnh: dùng nhiều trong giải tích số, hàm Möbius μ(n).

    • Định dạng đầu vào:

      Một số nguyên n (1 ≤ n ≤ 1.000.000).

    • Ràng buộc đầu vào:

      1 ≤ n ≤ 1.000.000. Không dùng math.h.

    • Định dạng đầu ra:

      1 nếu n square-free, 0 nếu không.

    Ví dụ:

    Đầu vào:

    30

    Đầu ra:

    1

    Giải thích:

    30 = 2·3·5, mọi mũ = 1 → square-free.

    Đang tải editor...