Maximum Distinct Prime Factors

You are given an array of n positive integers. Your task is to determine the maximum number of distinct prime factors among all the numbers in the array.

For a given positive integer \( n \), let \( pf(n) \) denote the number of distinct prime numbers that divide \( n \). For example:

• \( pf(10) = 2 \) (since \(10 = 2 \times 5\))
• \( pf(15) = 2 \) (since \(15 = 3 \times 5\))
• \( pf(30) = 3 \) (since \(30 = 2 \times 3 \times 5\))
• \( pf(1) = 0 \)

Your goal is to compute the maximum value of \( pf(x) \) where \( x \) is an element in the array.

Note: The number 1 has no prime factors, so its count is 0.

inputFormat

The first line contains a single integer \( n \) (the number of elements in the array).

The second line contains \( n \) space-separated integers representing the elements of the array.

outputFormat

Output a single integer — the maximum number of distinct prime factors among all numbers in the array.

5
10 15 21 17 30

3