NGTO3 - Nguyên tố cùng nhau (ACMVN 9-2014)
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 256 megabyte
Đăng bởi: admin

      Hai số nguyên dương được gọi là nguyên tố cùng nhau nếu có ước số chung lớn nhất là 1. Một tập  các số nguyên được gọi là tập số nguyên tố cùng nhau từng cặp nếu với mọi cặp số (a, b) thuộc tập này thì a, b nguyên tố cùng nhau.

      Cho một tập S gồm N số nguyên dương đầu tiên. Hãy tìm tập con lớn nhất của S (ký hiệu S') sao cho S' là tập số nguyên tố cùng nhau từng cặp.

Dữ liệu vào:

- Dòng thứ nhất là số nguyên T (1 ≤ T ≤ 1000) là số lượng test.

- Trong T dòng tiếp theo, mỗi dòng là một số nguyên N ứng với test cần thực hiện (1 ≤ N ≤ 106)

Dữ liệu ra:

- Ứng với mỗi test in ra một dòng sau đây "Case #i: p", trong đó i là thứ tự test và p là kích thước của tập số nguyên tố từng cặp lớn nhất ứng với test case đó.

Ví dụ

  • input
    1
    5
    output
    Case #1: 4
  • input
    2
    5
    8
    output
    Case #1: 4
    Case #2: 5

Trong test ứng với N = 5,  {1, 2, 3, 5} hoặc { 1, 3, 4, 5} là tập số nguyên tố từng cặp lớn nhất.

Back to Top