Count Primes

Moderate
0/80
Average time to solve is 50m
profile
Contributed by
62 upvotes
Asked in companies
DirectiIntuitHCL Technologies

Problem statement

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}.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
35
Sample Output 1:
5 7
Explanation For Sample Output 1:
Unique prime factors are 5 and 7.

Hence we return {5, 7}.
Sample Input 2:
14
Sample Output 2:
2 7
Constraints:
1 <= 'N' <= 10^6

Time Limit: 1 sec.
Hint

Try to use sieve of Eratosthenes.

Approaches (1)
Sieve of Eratosthenes

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’.

 

Time Complexity

O(Nlog(log(N))), where ‘N’ is the given number.

 

We are using the Sieve of Eratosthenes, so our complexity is O(Nlog(log(N))).

Space Complexity

O(N), where ‘N’ is the given number.

 

We are creating an array/vector of size ‘N’, so the space complexity is O(N).

Code Solution
(100% EXP penalty)
Count Primes
Full screen
Console