Count Primes Problem - Interview Kickstart

Example

Input: [6, 2, 5, 8]

Output: “0110”

6 is not a prime number. (6 = 2 * 3)

2 is a prime number.

5 is a prime number.

8 is not a prime number. (8 = 2 * 4)

Notes

Input Parameters: Function has one argument, an integer array.

Output: Return a string of the length equal to the size of the input array. For each number in the array the string has to have either “0” (not prime) or “1” (prime) character.

Constraints:

● 1 <= any input array element <= 4 * 10^6

● 1 <= number of array elements <= 3 * 10^5

Solution

We provided three sample solutions plus some notes in the very end.

1. brute_force_solution.cpp

For any number a[i], we iterate over 2 to a[i] - 1 and check if any of them divides a[i] or not. If we find at least one number that divides a[i] then a[i] is not a prime number.

Time Complexity:

O(N * MAX_A).

Auxiliary Space Used:

O(1).

Space Complexity:

O(N).


// -------- START --------

const int MAX_N = 300000, MAX_A = 4000000;

int check_if_prime(int no)
{
	if (no == 1)
	{
		return 0;
	}
	for (int i = 2; i < no; i++)						
	{
		if (no % i == 0)
		{
			return 0;
		}
	}
	return 1;
}

string detect_primes(vector a)
{
	int N = a.size();
	string ans(N, '0');
	for (int i = 0; i < N; i++)
	{
		if (check_if_prime(a[i]))
		{
			ans[i] = '1';
		}
		else
		{
			ans[i] = '0';
		}
	}
	return ans;
}

// -------- END --------

2. sub_optimal_solution.cpp

Any positive number x, which is non-prime (and not 1), can be written as x = a * b where a > 1 and b > 1. Here both a and b can not be > root(x), because if a > root(x) and b > root(x) then, a * b > root(x) * root(x), hence a * b > x, which contradicts a * b = x. When number is a square like 16 then it can be written as root(16) * root(16). So, non-prime number x can be written as a * b having at least one of them <= root(x). Now in the previous solution for each a[i], loop from root(a[i]) + 1 to a[i] - 1 is not necessary. Time complexity improves.

Time Complexity:

O(N * root(MAX_A)).

Auxiliary Space Used:

O(1).

Space Complexity:

O(N).


// -------- START --------

const int MAX_N = 300000, MAX_A = 4000000;

int check_if_prime(int no)
{
    if (no == 1)
    {
        return 0;
    }
    for (int i = 2; i * i <= no; i++)                       
    {
        if (no % i == 0)
        {
            return 0;
        }
    }
    return 1;
}

string detect_primes(vector a)
{
    int N = a.size();
    string ans(N, '0');
    for (int i = 0; i < N; i++)
    {
        if (check_if_prime(a[i]))
        {
            ans[i] = '1';
        }
        else
        {
            ans[i] = '0';
        }
    }
    return ans;
}

// -------- END --------

3. optimal_solution.cpp

Still we can improve. We can write any composite number as multiplication of prime numbers. Like 60 = 2 * 2 * 3 * 5. So, when we find any prime number, we can visit all the multiple of it and mark them as visited (non-prime). We start from 2 as base case, consider 2 as prime number and mark all its multiples 4, 6, 8, 10, ... as visited (non-prime) because they are multiples of 2. After considering 2, we will consider 3. Now, 3 is not marked as visited, which means, there are no factors of 3 and it is a prime number. Hence for 3 also, we do the same thing, mark all its multiples 6, 9, 12, 15 ... as visited (non-prime), because they are multiple of 3. Now 4 comes, but 4 is marked as visited by 2, so we know that 4 is not a prime number. Here also we can do the same thing: mark all its multiples 8, 12, 16 ... as visited, but all those positions are already marked as visited by 2, because all multiples of 4 are also multiples of 2. So, no need to do rework! Now, we keep on following the same steps for next numbers. Try to find prime numbers till 30 and you will get a more clear idea.

Still there can be some optimizations. When we find any prime number like 11, we mark 22, 33. 44, 55, 66 ... them as non-prime, but 22, 33, 44, 55 are already visited by smaller prime numbers. Like 22 is visited by 2, 33 is visited by 3, 44 is visited by 4 ... 110 is visited by 10. So, instead of starting marking multiples as non-prime from x+x, we can start from x*x.

This algorithm is called "Sieve of Eratosthenes".

Time Complexity:

O(N * log(log MAX_A)).

Auxiliary Space Used:

O(MAX_A).

Space Complexity:

O(N).


// -------- START --------

const int MAX_N = 300000, MAX_A = 4000000;

bool is_prime[MAX_A + 1];

void pre_process(int N, int max_value)
{
	fill_n(&is_prime[0], max_value + 1, true);
	// IMP. 1 is not a prime no.
	is_prime[1] = false;
	// i <= max_value is also correct but this is more efficient.
	for (int i = 2; i * i <= max_value; i++)
	{
	    /*
	    If not a prime no, then its multiples would have been already visited by
	    its prime factors previously. e.g. for i = 4, its multiples would have
	    been already visited by its prime factor 2.
	    */
	    if (!is_prime[i])
	    {
	        continue;
	    }
		/*
		In most of the implementations people start from j = i + i, but
		this will be just  waste of time. Think when i = 5 now we can visit
		like 10, 15, 20, 25, 30, 35... but here note that 10 = 2 * 5 so
		when i = 2 we have already marked it, same for 15 = 3 * 5 so when
		i = 3 we have already marked it! So it is same as starting from
		i * i. But directly starting from i * i will save time! 
		*/
		for (int j = i * i; j <= max_value; j += i)							
		{
			is_prime[j] = false;
		}
	}
}

string detect_primes(vector a)
{
	int N = a.size();

	pre_process(N, *max_element(a.begin(), a.end()));
	
	string ans(N, '0');
	for (int i = 0; i < N; i++)
	{
		if (is_prime[a[i]])
		{
			ans[i] = '1';
		}
	}
	return ans;
}

// -------- END --------

General notes and comparison of algorithms

Can we say that solution with time complexity O(N * log(log MAX_A)) is always better than solution with time complexity O(N * root(MAX_A))? No. It depends on the situation. In terms of time complexity of course it is better, but we should also consider space! Solution with time complexity O(N * root(A)) requires O(1) extra space, but other needs O(MAX_A) extra space. So, when space is more important than time, we should opt for the slower one.

If given a single integer and need to find if it is a prime or not, should we use Sieve of Eratosthenes? Probably not. We can check one number in O(root(A)) by iterating over 2 to root(A). Sieve of Eratosthenes algorithm is helpful when a) many numbers need to be checked and so the pre-processing can help and b) if those numbers are limited to a given range - so that we can estimate how much space the algorithm would use.

In this problem we are given the range for the numbers. But when given a stream of random numbers and nothing is specified about range of a[i] then we can use caching. Caching will be useful only when some numbers are going to repeat, though in real life that is likely to happen. We maintain two hash-tables. One containing prime numbers encountered until now and other containing non-prime numbers encountered. For each number, we check the presence in our hash tables and if it is present in one, we are done. If it is not present in either however, we use the O(root(number)) method to check if it is prime and add it into the appropriate hash table for future reference.

To further improve auxiliary space, we can check even numbers without adding them to the hashmap. Other optimizations can be considered in a real life implementation.