Array segregation of prime and composite numbers in C++

Array segregation typically refers to the process of categorizing or organizing elements within an array based on certain criteria or conditions. When dealing with an array of integers that include prime and composite numbers, the task is to separate these numbers into distinct groups: prime numbers and composite numbers. A prime number is defined as a positive number greater than 1 that has exactly two distinct divisors: 1 and itself. On the other hand, composite numbers have more than two positive divisors, including 1 and themselves.

Say we have an array of prime and composite numbers. Let’s move all prime numbers to the left and the composite numbers to the right.

Sample input

There are several approaches for solving this problem. Here are a few possible approaches:

1. Counting approach

In this approach, we can create two separate arrays for prime and composite numbers and traverse the original array to fill the prime and composite arrays (while keeping track of the number of prime and composite numbers). Finally, we can concatenate the prime array followed by the composite array to get the segregated array.

Code

The C++ program below first determines whether a number is prime. It then iterates through the array, categorizing each number as prime or composite and storing them in separate arrays (primes and composites). Finally, it prints out the prime array, the composite array, and the segregated array (prime numbers followed by composite numbers).

#include <iostream>
bool isPrime(int num) {
    if (num < 2) {
        return false;
    }
    for (int i = 2; i * i <= num; ++i) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}
int main() {
    const int capacity = 10;
    int input[capacity] = {4, 5, 7, 8, 9, 3, 2, 6, 1, 0};
    int primes[capacity] = {} , composites[capacity] = {}; // arrays to store the prime and composite numbers
    int primeCount = 0, compositeCount = 0; // counters to count the number of prime and composite numbers 
    for (int i = 0; i < capacity; i++) {
        int num = input[i];
        if (num == 0 || num == 1)
            continue; // skips the rest of the current iteration of the loop and moves to the next iteration
        if (isPrime(num)) {
            primes[primeCount++] = num;
        } else {
            composites[compositeCount++] = num;
        }
    }
    // Output the prime numbers
    std::cout << "Prime Array: ";
    for (int i = 0; i < primeCount; i++) {
        std::cout << primes[i] << " ";
    }
    std::cout << std::endl;
    // Output the composite numbers
    std::cout << "Composite Array: ";
    for (int i = 0; i < compositeCount; i++) {
        std::cout << composites[i] << " ";
    }
    std::cout << std::endl;
    // Output the segregated array
    std::cout << "Segregated Array: ";
    for (int i = 0; i < primeCount; i++) {
        std::cout << primes[i] << " ";
    }
    for (int i = 0; i < compositeCount; i++) {
        std::cout << composites[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}

Code explanation

Lines 3–13: The isPrime function first checks if the number num is less than 2. If it is, the function immediately returns false because prime numbers are greater than 1. It then checks if a number is prime by iterating from 2 to the square root of the number and checking if it divides the number evenly. If it doesn’t, then the number is a prime number and isPrime returns true.
Lines 21–28: The for loop iterates through the input array. If the numbers are 1 and 0, we skip them as they are neither prime nor composite. We then check each number with the isPrime function. If the number is prime, it is added to the primes array and primeCount is incremented. Otherwise, it is added to the composites array and compositeCount is incremented.
Lines 31–52: Finally, it prints out the prime array, the composite array, and the segregated array.

Time and space complexity

The time complexity of the code is $O(capacity * sqrt(m))$ where capacity is the size of the input array and m is the maximum value in the input array. This is because the code iterates through each element in the array (up to capacity) and for each element, the isPrime function checks if the number is prime by iterating up to sqrt(m). Therefore, the time complexity is $O(capacity * sqrt(m))$ .

The space complexity is $O(capacity)$ for the input array and $O(capacity)$ each for the primes and composites arrays, resulting in a total space complexity of $O(capacity)$ .

2. In-place segregation

In this approach, we segregate the prime and composite numbers without creating any extra array. This approach includes the following:

It uses the input array itself for segregating prime and composite numbers.
It uses two index variables (primeIndex and compositeIndex) to keep track of positions where prime and composite numbers are to be placed.
Prime numbers are swapped to the beginning of the array (input) as they are identified, using std::swap.
After the loop completes, prime numbers occupy the initial segment of the array, and composite numbers occupy the segment following the prime numbers.

Code

#include <iostream>
#include <algorithm>
bool isPrime(int num) {
    if (num < 2) {
        return false;
    }
    for (int i = 2; i * i <= num; ++i) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}
int main() {
    const int capacity = 10;
    int input[capacity] = {4, 5, 7, 8, 9, 3, 2, 6, 1, 0};
    int primeIndex = 0, compositeIndex = 0; // variables to keep track of the positions where prime and composite numbers will be placed in the array, respectively
    for (int i = 0; i < capacity; i++) {
        int num = input[i];
        if (num == 0 || num == 1)
            continue; 
        if (isPrime(num)) {
            std::swap(input[i], input[primeIndex]);
            primeIndex++;
        }
        else 
            compositeIndex++;
    }
    // Output the prime numbers
    std::cout << "Prime Numbers: ";
    for (int i = 0; i < primeIndex; i++) {
        std::cout << input[i] << " ";
    }
    std::cout << std::endl;
    // Output the composite numbers
    std::cout << "Composite Numbers: ";
    for (int i = 0; i < compositeIndex; i++) {
        std::cout << input[i + primeIndex] << " ";
    }
    std::cout << std::endl;
    // Output the segregated array
    std::cout << "Segregated Array: ";
    for (int i = 0; i < primeIndex + compositeIndex; i++) {
        std::cout << input[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}

Code explanation

Line 19: Two variables primeIndex and compositeIndex are initialized to 0. These variables keep track of the positions where prime and composite numbers will be placed in the input array, respectively.

Lines 21–31: The for loop iterates through each element of the input array. For each non-zero, non-one number, we check if it is prime using the isPrime function. If it is prime, we swap it with the element at the primeIndex and increment primeIndex. If it is composite, we increment compositeIndex. This prepares for storing composite numbers sequentially after the prime numbers in the input array.

Lines 33–52: After processing all numbers, we’ve printed the prime numbers, the composite numbers, and the segregated array. The prime numbers are output first, followed by the composite numbers, and finally, the segregated array is printed as a combination of the prime and composite numbers.

Time and space complexity

The time complexity of the code is $O(capacity * sqrt(m))$ , where capacity is the size of the input array and m is the maximum value in the input array.

The space complexity of the code is $O(1)$ , as it uses a constant amount of extra space regardless of the input size.

Conclusion

In summary, approach 1 (using separate arrays) offers clarity and straightforwardness but at the cost of additional space. Approach 2 (in-place segregation) is more space-efficient and potentially more optimal in terms of time complexity, though it requires careful handling of array indices and swapping logic. The choice between them would depend on specific requirements like space constraints and performance considerations in a given context.

Free Resources