PRIMFACT05 - Editorial

editorial
, , ,
1

Problem Link - Prime Distinctness in Number theory

Problem Statement:

Given a positive integer N, the objective is to determine whether integer N is prime or not. If N is prime or 1, the function should return 1. Otherwise, if N is not prime, the task is to calculate and return the count of distinct prime factors of N.

Approach:

  1. Understanding the Problem: Check if a positive integer N is prime and, if not, count the distinct prime factors.

  2. Prime Checking and Factorization:

  • If the input number is 1 or 2, it directly outputs 1 since both are not considered to have prime factors.
  • Use a method to calculate the prime factors of n. An unordered set is used to store distinct prime factors. Sets automatically handle duplicates, ensuring only unique prime factors are counted.
  • Finding Prime Factors:Iterates from 2 to √n to find prime factors. If n is divisible by i, it divides n and stores i in the set. If n is still greater than 1 after the loop, it is a prime factor itself.
  • Finally, the size of the set gives the count of distinct prime factors.

Complexity:

  • Time Complexity: O(√N) For calculating the prime numbers.
  • Space Complexity: O(√N) At the worst case the set can store up to √N number of prime factors.