Last Updated: 21 Jun, 2021
Count Primes
Moderate
Asked in companies
You are given an integer 'N'.
You must return the unique prime factors of 'N' in increasing order.
For Example:
For ‘N’ = 10.
Unique prime factors are 2 and 5.
Hence we return {2, 5}.
Input Format:
The only line contains a single integer 'N'.
Output Format:
The only lines contain the unique prime factors of 'N'.
Note:
You are not required to print anything; it has already been handled. Just implement the function.
Approaches
Approach:
- Sieve of Eratosthenes works by putting all the numbers till ‘N’ as true and checking if the number is prime or not from 2. if it finds that 2 is prime(that, of course, is), then it marks all its multiple as false, and it repeatedly does it till it reaches N(it reduces time by checking if it is true or not).
- Initialize an empty array ‘ans’.
- Make a new bool vector initialized with true and of size(N+1);
- Now make a loop initialized with 2 and till N, and inside the loop, if the prime is true and it is a factor of ‘N’, push it in ‘ans’ array. and also another loop that eliminates all its multiple till n.
- Then return the ‘ans’.
Similar problems