Brute Force Approach
This approach considers checking all the elements in the ‘input’ array for their prime nature and then storing the element in its respective vector according to its nature.
Steps of Algorithm
Step 1. Create a function ‘getResult()’ that will accept two parameters, i.e., one vector of integer ‘input’, and the second one is the ‘N’ - the size of the vector ‘input’.
Step 2. Create two vectors ‘main_primes’ and ‘main_non_primes’, to store prime and the non-prime numbers.
Step 3. Make an iteration using the ‘for’ loop using the ‘i’ variable in which we need to check whether the element at ‘ith’ index is prime or not by passing the element in the ‘get_prime’ function.
Step 4. In the ‘get_prime’ function, check for the edge cases, i.e., 1, 2, or 3. If the element passes through the edge cases condition, then skip for middle five numbers, and then even if it’s also passed, then we need to make an iteration using the ‘for’ loop, which will check if there’s any number that is the factor of that element, if there exists a factor, then return 0, reflecting that a number is a non-prime number, else after the iteration, return 1, reflecting that an element is a prime number.
Step 5. Accumulate all the prime numbers on the left side of the ‘input’ vector using an iteration, and then accumulate all the non-prime numbers on the right side of the ‘input’ vector using an iteration.
Step 6. Print the modified ‘input’ vector.
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
int get_prime(int x)
{
// Edges Cases
if (x <= 1)
{
// 1 is neither prime nor composite
return 0;
}
if (x == 3 || x == 2)
{
// Number 2 and 3 both are prime
return 1;
}
// Skip middle five numbers
if (x % 2 == 0 || x % 3 == 0)
{
return 0;
}
// Checks for prime or non prime nature using this iteration
for (int i = 5; i * i <= x; i = i + 6)
{
// If there exist any factor of a number, then its not a prime number
if (x % i == 0 || x % (i + 2) == 0)
{
return 0;
}
}
return 1;
}
void getResult(vector<int> &input, int n)
{
// Vector to store all the prime numbers
vector<int> main_primes;
// Vector to store all the non-prime numbers
vector<int> main_non_primes;
// Store all the prime and non-prime elements from 'input' vector separately
for (int i = 0; i < n; i++)
{
if (get_prime(input[i]) == 1)
{
main_primes.push_back(input[i]);
}
else
{
main_non_primes.push_back(input[i]);
}
}
// Store all prime numbers on left side of the 'input' vector
int i = 0;
while (i < main_primes.size())
{
input[i] = main_primes[i];
i++;
}
// Store all non-prime numbers on right side of the 'input' vector
int j = 0;
while (j < main_non_primes.size())
{
input[i] = main_non_primes[j];
i++;
j++;
}
return;
}
int main()
{
vector<int> input = { 20, 13, 41, 5, 1, 2, 9, 19, 14 };
int n = input.size();
cout << "Input Array:- ";
for (int i = 0; i < n; i++)
{
cout << input[i] << " ";
}
cout << endl;
cout << "Array after segregation of primes and non-prime: ";
getResult(input, n);
for (int i = 0; i < n; i++)
{
cout << input[i] << " ";
}
cout << endl;
return 0;
}
Output
Input Array:- 20 13 41 5 1 2 9 19 14
Array after segregation of primes and non-prime: 13 41 5 2 19 20 1 9 14
Complexity Analysis
Time Complexity: O(N * sqrt(N))
Incall to ‘getResult()’, we are using a loop to check for the prime nature of each element of the array which will take ‘N * sqrt(N)’ computational time, therefore, the overall time complexity is O(N * sqrt(N)), where ‘N’ is the size of the ‘input’ vector.
Space Complexity: O(N)
As we are using two vectors to store all the prime and the non-prime numbers, therefore, the overall space complexity will be O(N).
Check out this problem - Search In Rotated Sorted Array
Efficient Approach
This approach considers storing all the prime numbers using the Sieve of Atkin algorithm and then checking each element using an iteration, in which if the value of ‘primes’ vector at ‘ith’ index is 1, then this reflects that the number is prime, where the value of ‘ith’ index is equal to the value of the element for which we need to check the prime nature.
Steps of Algorithm
Step 1. Create a function ‘get_Result()’ that will accept two parameters, i.e., one vector of integer ‘input’, and the second one is the ‘N’ - the size of the vector ‘input’.
Step 2. Create a vector ‘primes’ of size 1000005, and initialize it with zero.
Step 3. Call the ‘get_prime’ function, in this function, we need to calculate the prime nature of the numbers and organize accordingly in the ‘primes’ vector.
Step 4. In the ‘get_primes’ function, calculate all the prime numbers by evaluating the conditions mentioned in the code, and then mark all the multiples of squares as non-prime
Step 5. As 1 is neither prime nor composite, so assign zero at the ‘1st’ index, and assign 1 as ‘2nd’ and ‘3rd’ index as both are prime numbers.
Step 6. Now in the ‘get_Result’ function, accumulate all the prime numbers on the left side of the ‘input’ vector using an iteration, and then accumulate all the non-prime numbers on the right side of the ‘input’ vector using an iteration.
Step 7. Print the modified ‘input’ vector.
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
// Function to generate prime numbers using Sieve Of Atkin
void get_primes(vector<int> &primes)
{
int x = primes.size();
// Calculate all the prime numbers using following conditions
for (int i = 1; i * i < x; i++)
{
for (int j = 1; j * j < x; j++)
{
int temp = (4 *i *i) + (j *j);
if (temp <= x && (temp % 12 == 1 || temp % 12 == 5))
{
primes[temp] ^= 1;
}
temp = (3 *i *i) + (j *j);
if (temp <= x && temp % 12 == 7)
{
primes[temp] ^= 1;
}
temp = (3 *i *i) - (j *j);
if (i > j && temp <= x && temp % 12 == 11)
{
primes[temp] ^= 1;
}
}
}
// 1 is neither prime nor composite
primes[1] = 0;
// 2 and 3 both are prime numbers
primes[2] = 1;
primes[3] = 1;
// All multiples of squares are non-prime
for (int i = 5; i * i < x; i++)
{
if (primes[i] == 1)
{
for (int j = i * i; j < x; j += i *i)
{
primes[j] = 0;
}
}
}
return;
}
// Function to accumulate all primes and non-prime numbers on left and right side of the 'input' vector respectively
void get_Result(vector<int> &input, int n)
{
// Generate all primes
vector<int> primes(1000005, 0);
get_primes(primes);
// Vector to store all the prime numbers
vector<int> main_primes;
// Vector to store all the non-prime numbers
vector<int> main_non_primes;
// Store all the prime and non-prime elements from 'input' vector separately
for (int i = 0; i < n; i++)
{
if (primes[input[i]] == 1)
{
main_primes.push_back(input[i]);
}
else
{
main_non_primes.push_back(input[i]);
}
}
// Store all prime numbers on left side of the 'input' vector
int i = 0;
while (i < main_primes.size())
{
input[i] = main_primes[i];
i++;
}
// Store all non-prime numbers on right side of the 'input' vector
int j = 0;
while (j < main_non_primes.size())
{
input[i] = main_non_primes[j];
i++;
j++;
}
return;
}
// Driver code
int main()
{
vector<int> input = { 20, 13, 41, 5, 1, 2, 9, 19, 14 };
int n = input.size();
cout << "Input Array:- ";
for (int i = 0; i < n; i++)
{
cout << input[i] << ", ";
}
cout << endl;
cout << "Array after segregation of primes and non-prime: ";
get_Result(input, n);
for (int i = 0; i < n; i++)
{
cout << input[i] << ", ";
}
cout << endl;
return 0;
}
Output
Input Array:- 20 13 41 5 1 2 9 19 14
Array after segregation of primes and non-prime: 13 41 5 2 19 20 1 9 14
Complexity Analysis
Time Complexity: O(N / (log (log N)))
Incall to ‘getResult()’, we are using the Sieve of Atkin algorithm to calculate all the prime numbers, which takes ‘N / (log log N)’ computational time, and after that, we are storing all the prime and the non-prime elements of the ‘input’ array using an iteration, which will take ‘N’ worst-case computational time, therefore, the overall time complexity is O(N / (log log N)), where ‘N’ is the size of the ‘input’ vector.
Space Complexity: O(N)
As we are using two vectors to store all the prime and the non-prime numbers, therefore, the overall space complexity will be O(N).
Frequently Asked Questions
What is the alternative to calculating prime nature?
We can use the following algorithms to calculate the prime nature:
- Sieve of Eratosthenes
- Sieve of Sundaram
Can we store the prime and the non-prime numbers on the right side, and the left side respectively?
Yes, we can segregate the prime and the non-prime numbers on the right and left sides respectively. There are no constraints on the side, we just have to collect both the prime and the non-prime on two different sides.
Can we segregate both the prime and non-prime numbers in an array without using auxiliary space?
Yes, we can segregate both the prime and non-prime numbers in an array without using auxiliary space. We can use two pointer method to traverse the array and swap accordingly.
Also Read - Strong number in c
Conclusion
In this article, we discussed segregating the prime and non-prime numbers in an array, discussed the various approaches to solve this problem programmatically, the time and space complexities, and how to optimize the approach to reducing the time complexity of the problem.
Check out this article on implementing the Sieve of Eratosthenes with Linear Time Complexity
Recommended Articles
Kth Smallest Prime Number in range L to R for Q queries
Find Prime Numbers in a 2D Array (Matrix)
Make two numbers equal by multiplying with their prime factors the minimum number of times
Do check out some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, etc. on Coding Ninjas Studio
Check out some of the amazing Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Basics of C, Basics of Java, etc. along with some Contests and Interview Experiences only on Coding Ninjas Studio.
Until then, all the best for your future endeavors, and Keep Coding.
39+ registered 