Exactly 3 Divisors

PHOTO EMBED

Sun Feb 06 2022 02:04:54 GMT+0000 (UTC)

Saved by @Uttam #java #mathematics #gfg #geeksforgeeks #exactly3divisors

import java.io.*;
import java.util.*;

class Solution
{
    public static boolean isPrime(int num)
    {
        if(num==1) return false;
        if(num==2 || num==3) return true;
        if(num%2==0 || num%3==0) return false;
        for(int i=5; i*i<=num; i+=6)
        {
            if(num%i==0 || num%(i+2)==0)
                return false;
        }
        return true;
    }

    public static int exactly3Divisors(int N)
    {
        int count = 0;
        for(int i=2; i*i<=N; i++)
        {
            if(isPrime(i))
                count++;
        }
        return count;
    }
}

class Main {
	public static void main (String[] args) {
		Scanner sc=new Scanner(System.in);

		//taking testcases
		int T=sc.nextInt();
		
		while(T-->0)
		{
		    Solution obj=new Solution();
		    int N;
		    N=sc.nextInt();//taking N
		    //calling function exactly3Divisors()
		    System.out.println(obj.exactly3Divisors(N));
		}
		
	}
}
content_copyCOPY

8. Exactly 3 Divisors Given a positive integer value N. The task is to find how many numbers less than or equal to N have numbers of divisors exactly equal to 3. Example 1: Input: N = 6 Output: 1 Explanation: The only number less than 6 with 3 divisors is 4. Example 2: Input: N = 10 Output: 2 Explanation: 4 and 9 have 3 divisors. Your Task: You don't need to read input or print anything. Your task is to complete the function exactly3Divisors() that takes N as input parameter and returns count of numbers less than or equal to N with exactly 3 divisors. Expected Time Complexity: O(N^1/2 * N^1/4) Expected Auxilliary Space: O(1) Constraints : 1 <= N <= 10^9

https://practice.geeksforgeeks.org/problems/exactly-3-divisors/1/?track=DSASP-Mathematics&batchId=190