Input: [6, 2, 5, 8]
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)
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.
● 1 <= any input array element <= 4 * 10^6
● 1 <= number of array elements <= 3 * 10^5
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).
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.
O(N * root(MAX_A)).
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)).
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.