Tập lớn nhất

Xem PDF

Điểm: 1800 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho dãy số nguyên dương \(A = (a_1, a_2, . . ., a_n)\). Hãy tìm tập nhiều phần tử nhất có cùng ít nhất
một ước số chung lớn lớn hơn 1 và đưa ra số phần tử trong tập tìm được.

Ví dụ, với \(A = (6, 15, 10, 42)\), tập {\(6, 10, 42\)} chứa các số cùng chia hết cho 2 và là tập nhiều phần
tử nhất có cùng ít nhất một ước số chung lớn lớn hơn 1. Số lượng các phần tử trong tập là 3.

Input

  • Dòng đầu tiên chứa số nguyên \(n\ (1 \le n \le 1000)\),
  • Dòng thứ 2 chứa \(n\) số nguyên \(a_1, a_2, . . ., a_n (2 \le a_i \le 10^{18}, i = 1 ÷ n)\).

Output

  • Đưa ra một số nguyên – số lượng phần tử của tập tìm được.

Example

Test 1

Input
4
6 15 10 42
Output
3

Bình luận

Không có bình luận nào.