Primes Behind the Product

Medium

You get an array of positive integers values. Imagine multiplying all of its elements together. How many different prime numbers divide that product? The product itself can be enormous, so actually computing it is not a good idea.

Example 1

values=[12, 35, 9] → 4

12 = 2²·3, 35 = 5·7 and 9 = 3². The product contains the primes 2, 3, 5 and 7, which makes four.

Example 2

values=[49, 7, 343] → 1

Every number is a power of 7, so there is only one prime factor.

Example 3

values=[997] → 1

Constraints

1 ≤ len(values) ≤ 10⁴
2 ≤ values[i] ≤ 10⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table Math Number Theory

Similar problems

Photo Frames of the Same Shape Medium Primes Along Grid Rays Medium Even Piles of Cards Easy Biggest Shared-Factor Group Hard First Coprime Cut Hard

Input

values=[12, 35, 9]

Expected

Run checks the first 3 tests in your browser. Submit checks all 114 tests on the server, hidden ones included.