Leetcode Problem 2521. Distinct Prime Factors of Product of Array

2521. Distinct Prime Factors of Product of Array

Leetcode Solutions

Sieve of Eratosthenes and Prime Factorization

  1. Initialize a list primes of size 1001 with True (assuming all numbers are prime initially).
  2. Use the Sieve of Eratosthenes to mark non-prime numbers in primes as False.
  3. Initialize an empty set unique_prime_factors to store unique prime factors.
  4. Iterate over each number in nums.
  5. For each number, divide it by each prime number in primes until it is no longer divisible.
  6. If the number is divisible by a prime, add that prime to unique_prime_factors.
  7. Continue the process until the number is reduced to 1.
  8. Return the size of unique_prime_factors as the result.
UML Thumbnail

Brute Force Prime Factorization

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...