Given an array of integers, check each number if it’s prime.
{
"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)
'0' (not prime) or '1' (prime) character.Constraints:
We provided three sample solutions plus some notes in the very end.
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.
O(N * MAX_A).
O(1).
O(N).
/*
* 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;
}
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.
O(N * root(MAX_A)).
O(1).
O(N).
/*
* 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;
}
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”.
O(N * log(log(MAX_A))).
O(MAX_A).
O(N).
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.
/*
* 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:
â€To learn more, register for the FREE webinar.
The 11 Neural “Power Patterns” For Solving Any FAANG Interview Problem 12.5X Faster Than 99.8% OF Applicants
The 2 “Magic Questions” That Reveal Whether You’re Good Enough To Receive A Lucrative Big Tech Offer
The “Instant Income Multiplier” That 2-3X’s Your Current Tech Salary
The 11 Neural “Power Patterns” For Solving Any FAANG Interview Problem 12.5X Faster Than 99.8% OF Applicants
The 2 “Magic Questions” That Reveal Whether You’re Good Enough To Receive A Lucrative Big Tech Offer
The “Instant Income Multiplier” That 2-3X’s Your Current Tech Salary
Just drop your name and email so we can send your Power Patterns PDF straight to your inbox. No Spam!
By sharing your contact details, you agree to our privacy policy.
Time Zone: Asia/Dhaka
We’ve sent the Power Patterns PDF to your inbox — it should arrive in the next 30 seconds.
📩 Can’t find it? Check your promotions or spam folder — and mark us as safe so you don’t miss future insights.
We’re hosting a private session where FAANG insiders walk through how they actually use these Power Patterns to crack interviews — and what sets top performers apart.
🎯 If you liked the PDF, you’ll love what we’re sharing next.
Time Zone:
