Detect Prime Numbers Problem Statement

Given an array of integers, check each number if it’s prime.

Example

{
"a": [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

• 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⁶
• 1 <= number of array elements <= 3 * 10⁵

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

Detect Prime Numbers Solution 1: Brute Force

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

Code For Detect Prime Numbers Solution 1: Brute Force

/*
* Asymptotic complexity in terms of size of \`a\` \`n\` and maximum element in \`a\` \`MAX_A\`:
* Time: O(n * MAX_A).
* Auxiliary space: O(1).
* Total space: O(n).
*/

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<int> &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;
}

Detect Prime Numbers Solution 2: Sub Optimal

Any positive number x, which is non-prime (and not 1), can be written as x = a * b where a > 1 and b > 1. Let root(x) be a function that returns square root of the provided number x. 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).

Code For Detect Prime Numbers Solution 2: Sub Optimal

/*
* Asymptotic complexity in terms of length of \`a\` \`n\` and maximum element in \`a\` \`MAX_A\`:
* Time: O(n * square_root(MAX_A)).
* Auxiliary space: O(1).
* Total space: O(n).
*/

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<int> &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;
}

Detect Prime Numbers Solution 3: Optimal

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

General notes and comparison of algorithms

Can we say that solution with time complexity O(N * log(log(MAXA))) is always better than solution with time complexity O(N * root(MAXA))? 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.

Code For Detect Prime Numbers Solution 3: Optimal

/*
* Asymptotic complexity in terms of size of \`a\` \`n\` and maximum element in \`a\` \`MAX_A\`:
* Time: O(n * log(log(MAX_A))).
* Auxiliary space: O(MAX_A).
* Total space: O(n).
*/

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<int> &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;
}

We hope that these solutions to counting primes problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart’s FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

• Back-end Engineering Interview Course
• Front-end Engineering Interview Course
• Full Stack Developer Interview Course

‍To learn more, register for the FREE webinar.