Prime with 3 factors
You are given an array ‘ARR’ consisting of ‘N’ positive integers. Your task is to find if the number has exactly 3 factors for each number in the array ‘ARR’.

You have to return an array consisting of ‘0,’ and ‘1’ where ‘0’ means that ‘ARR[index]’ does not have 3 factors and ‘1’ means ‘ARR[index]’ has exactly 3 factors.

For Example:

If ‘N’ = 4 and ‘ARR’ = [3, 5, 4, 2]. 3 has 2 factors, which are 1 and 3. 5 has 2 factors, which are 1 and 5. 4 has 3 factors, which are 1, 2 and 4. 2 has 2 factors, which are 1 and 2. Hence, the answer is [0, 0, 1, 0].

Input format :

The first line contains a single integer ‘T’ representing the number of test cases. The first line of each test case contains a single integer ‘N’ denoting the number of elements in the array. The next line contains ‘N’ space-separated integers denoting the elements of array ‘ARR’.

Output format :

For each test case, print an array containing 0 and 1 where 1 is present if the number ‘ARR[index]’ has exactly 3 factors. Otherwise, 0 is present. Print the output of each test case in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1

Question

Prime with 3 factors

You are given an array ‘ARR’ consisting of ‘N’ positive integers. Your task is to find if the number has exactly 3 factors for each number in the array ‘ARR’.

You have to return an array consisting of ‘0,’ and ‘1’ where ‘0’ means that ‘ARR[index]’ does not have 3 factors and ‘1’ means ‘ARR[index]’ has exactly 3 factors.

For Example:

If ‘N’ = 4 and ‘ARR’ = [3, 5, 4, 2]. 
3 has 2 factors, which are 1 and 3.
5 has 2 factors, which are 1 and 5.
4 has 3 factors, which are  1, 2 and 4.
2 has 2 factors, which are 1 and 2.
Hence, the answer is [0, 0, 1, 0].

Input format :

 The first line contains a single integer ‘T’ representing the number of test cases.

The first line of each test case contains a single integer ‘N’ denoting the number of elements in the array.

The next line contains ‘N’ space-separated integers denoting the elements of array ‘ARR’.

Output format :

For each test case, print an array containing 0 and 1 where 1 is present if the number ‘ARR[index]’ has exactly 3 factors. Otherwise, 0 is present.

Print the output of each test case in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

 1 <= T <= 10
 1 <= N <= 10^6
 1 < ARR[index] <= 10^12

Time Limit: 1 second

Accepted Answer

Step 1 : While n is divisible by 2, print 2 and divide n by 2.
Step 2 : After step 1, n must be odd. Now start a loop from i = 3 to square root of n. While i divides n, print i and divide n by i. After i fails to divide n, increment i by 2 and continue.
Step 3 : If n is a prime number and is greater than 2, then n will not become 1 by above two steps. So print n if it is greater than 2.

Accepted Answer

Brute Force

In this approach, we will implement a function in which we have to pass an integer, and for each integer passed, the function returns the number of factors of that number. So we iterate over the input array ARR, and we pass each ARR[index] to this function. If it returns 3, the result[index] is set to 1. Otherwise, it is set to 0. In the end, we will return the array result.

Algorithm:

Make a function countFactors(num). This function returns the number of factors corresponding to the num.
Initialize a variable numOfFactors with 0.
Iterate ind from 1 to num:
- If num is divisible by ind then increment numOfFactors with 1.
Return numOfFactors, which is the total number of factors of num.
Make a function named hasThreeFactors(ARR,N). This function will return an array result that contains values 0 or 1.
- Create a result array of size N.
- Iterate ind from 0 to N - 1:
  - If countFactors(ARR[ind]) is equal to 3 then set result[ind] as 1. Otherwise set result[ind] as 0.
- Return the result array.

Space Complexity: O(n)Explanation:

O(N) where N is the number of elements in the input array.

The space complexity O(N) is used to make the result array. Hence, the overall space complexity is O(N).

Time Complexity: OtherExplanation:

O(N * Max(ARR)) where N is the number of elements in the input array.

For each element of the array ARR, we have to traverse from 1 to that element value. Hence, the overall time complexity is O(N * Max(ARR)).

Java (SE 1.8)


/*
	Time Complexity: O(N * Max(ARR))
	Space Complexity: O(N)
	
	where N is the number of elements in the input array.
*/

public class Solution {
	public static int countFactors(int num) {

		// Variable to count number of factors
		int numOfFactors = 0;

		for (int ind = 1; ind < num + 1; ++ind) {

			// If ind is factor of num
			if ((num % ind) == 0) {
				numOfFactors = numOfFactors + 1;
			}
		}

		// Return number of factors
		return numOfFactors;
	}

	public static int[] hasThreeFactors(int[] arr, int n) {

		// Maintain a result array to store result
		int[] result = new int[n];

		for (int ind = 0; ind < n; ++ind) {

			// If index element has 3 factors
			if (countFactors(arr[ind]) == 3) {
				result[ind] = 1;
			} else {
				result[ind] = 0;
			}
		}

		// Return result array
		return result;
	}

}

Python (3.5)

"""

Time Complexity: O(N * Max(ARR))

Space Complexity: O(N)



where N is the number of elements in the input array.

"""





def countFactors(num):



    # Variable to count number of factors

    numOfFactors = 0



    for ind in range(1, num + 1):



        # If ind is factor of num

        if((num % ind) == 0):

            numOfFactors = numOfFactors + 1



    # Return number of factors

    return numOfFactors





def hasThreeFactors(arr, n):



    # Maintain a result array to store result

    result = []



    for ind in range(n):



        # If index element has 3 factors

        if(countFactors(arr[ind]) == 3):

            result.append(1)

        

        else:

            result.append(0)



    # Return result array

    return result

C++ (g++ 5.4)

/*

Time Complexity: O(N * Max(ARR))

Space Complexity: O(N)



where N is the number of elements in the input array.

*/





int countFactors(int num)

{

    // Variable to count number of factors

    int numOfFactors = 0;



    for(int ind = 1; ind < num + 1; ++ind)

    {

        // If ind is factor of num

        if((num % ind) == 0)

        {

            numOfFactors = numOfFactors + 1;

        }

    }



    // Return number of factors

    return numOfFactors;

}



vector hasThreeFactors(vector &arr, int n) 

{

    // Maintain a result array to store result

    vector result(n);



    for(int ind = 0; ind < n; ++ind)

    {

        // If index element has 3 factors

        if(countFactors(arr[ind]) == 3)

        {

            result[ind] = 1;

        }

        else

        {

            result[ind] = 0;

        }

    }



    // Return result array

    return result;

}

Accepted Answer

Sieve Of Eratosthenes

In this approach, we will make a sieve array that maintains whether that particular index is a prime number or not. If the index is a prime number, then the sieve[index] is equal to 1. Otherwise, sieve[index] is equal to 0.

Now, after this, we have to traverse the input array ARR

if ARR[ind] is 1, then set result[ind] to 0 and move to the next element.
We will check if ARR[ind] is a perfect square and its square root is a prime, then set result[ind] as 1. Otherwise, set result[ind] as 0.

Algorithm:

Create a function hasThreeFactors(ARR,N). This function will return an array result that contains values 0 or 1.
- Create a result array of size N.
- Set the variable length as the minimum of the value 1000001 and Max(ARR).
- Create a sieve array of size length and initialize all elements with 0.
- Set ind as 2.
- We will iterate till the square of ind is less or equal to length.
  - We will check If sieve[ind] is equal to 0.
    - Set ind1 as 2 * ind.
    - We will iterate till ind1 is less than or equal to length. We will set sieve[ind1] as 1 and increment ind1 by ind.
- Iterate ind from 0 to N-1:
  - If ARR[ind] is equal to 1 then set result[ind] as 0 and move to the next element.
  - If ARR[ind] is a perfect square and sieve[sqrt(ARR[ind])] is 0 then set result[ind] as 1. Otherwise set result[ind] as 0.
- Return the result array.

Space Complexity: OtherExplanation:

O(length + N) where N is the number of elements in the input array and length is the size of the sieve array.

The space complexity O(N) is used to make the result array. The space complexity O(length) is used to make the sieve array. Hence, the overall space complexity is O(length + N).