Distinct Prime Factors
MediumPractice library · +20 XPmathnumber theoryprimes
Given a list of N integers, find the total count of distinct prime factors across all the numbers in the list. For example, if the list is [10, 12, 15], the prime factors are 2, 5 (for 10), 2, 3 (for 12), and 3, 5 (for 15). The distinct prime factors are 2, 3, and 5. The total count is 3.
Input
The first line contains an integer N, the number of integers in the list. The second line contains N space-separated integers a_1, a_2, ..., a_N.
Output
Print a single integer, the total count of distinct prime factors of all numbers in the list.
Constraints
1 <= N <= 200000, 2 <= a_i <= 10^6
Time limit 2 s (native code; slower languages get more)Memory 256 MB13 hidden tests
Example 1
Input
3 10 12 15
Output
3
Prime factors of 10 are {2, 5}, 12 are {2, 3}, 15 are {3, 5}. Distinct primes are {2, 3, 5}. Count is 3.
Example 2
Input
4 7 11 13 17
Output
4
All numbers are prime. Distinct primes are {7, 11, 13, 17}. Count is 4.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
3 10 12 15
Example 2 input
4 7 11 13 17