# Generate all prime partition of a number

Prime partition refers to the process of dividing a given number into a set of prime numbers. For example, if the number is 6, it can be partitioned as 2 + 2 + 2 or 3 + 3. The objective of generating all prime partitions of a given number is to list down all the possible ways to divide the number into prime numbers.

To generate all prime partitions of a number, we can use a recursive approach. First, we identify the prime numbers that can be used for the partition. Then we take each prime number and recursively partition the remaining number until we reach a partition where all the numbers are prime.

## Code Solution

``````// C program for
// Generate all prime partition of a number
#include <stdio.h>

// Find all prime numbers which have smaller and equal to given number n
void sieveOfEratosthenes(int prime[], int n)
{
// Initial two numbers are not prime (0 and 1)
prime[0] = 0;
prime[1] = 0;
// Set the initial (2 to n element is prime)
for (int i = 2; i <= n; ++i)
{
prime[i] = 1;
}
// We start to 2
for (int i = 2; i *i <= n; ++i)
{
if (prime[i] == 1)
{
// When i is prime number
// Modify the prime status of all next multiplier of location i
for (int j = i *i; j <= n; j += i)
{
prime[j] = 0;
}
}
}
}
// Display calculated result
void printData(int result[], int size)
{
printf("\n");
for (int i = 0; i < size; ++i)
{
printf(" %d", result[i]);
}
}
void partition(int value, int prime[], int result[], int index, int sum, int num)
{
if (sum == num)
{
// Print the result
printData(result, index);
return;
}
if (index >= num / 2 || sum > num)
{
// Use to stop process
// 1) When sum is greater than num or
// 2) index is outside the limit
return;
}
for (int i = value; i <= num; ++i)
{
if (prime[i] == 1)
{
// When i is prime
result[index] = i;
// Find next element
partition(i, prime, result, index + 1, sum + i, num);
}
}
}
void primePartition(int num)
{
if (num <= 1)
{
return;
}
// This are collecting prime number
int prime[num + 1];
// Use to collect result
int result[num / 2];
// Find prime number
sieveOfEratosthenes(prime, num);
// Display given number
printf("\n Given number : %d", num);
// Find partition
partition(2, prime, result, 0, 0, num);
}
int main()
{
// Test
primePartition(7);
primePartition(17);
primePartition(9);
return 0;
}``````

#### Output

`````` Given number : 7
2 2 3
2 5
7
Given number : 17
2 2 2 2 2 2 2 3
2 2 2 2 2 2 5
2 2 2 2 2 7
2 2 2 2 3 3 3
2 2 2 3 3 5
2 2 2 11
2 2 3 3 7
2 2 3 5 5
2 2 13
2 3 3 3 3 3
2 3 5 7
2 5 5 5
3 3 3 3 5
3 3 11
3 7 7
5 5 7
17
Given number : 9
2 2 2 3
2 2 5
2 7
3 3 3``````
``````/*
Java program
Generate all prime partition of a number
*/
public class Partitions
{
// Find all prime numbers which have smaller and equal to given number n
public void sieveOfEratosthenes(boolean[] prime, int n)
{
// Initial two numbers are not prime (0 and 1)
prime[0] = false;
prime[1] = false;
// Set the initial (2 to n element is prime)
for (int i = 2; i <= n; ++i)
{
prime[i] = true;
}
// We start to 2
for (int i = 2; i * i <= n; ++i)
{
if (prime[i] == true)
{
// When i is prime number
// Modify the prime status of all next multiplier of location i
for (int j = i * i; j <= n; j += i)
{
prime[j] = false;
}
}
}
}
// Display calculated result
public void printData(int[] result, int size)
{
System.out.print("\n");
for (int i = 0; i < size; ++i)
{
System.out.print(" " + result[i]);
}
}
public void partition(int value, boolean[] prime, int[] result, int index, int sum, int num)
{
if (sum == num)
{
// Print the result
printData(result, index);
return;
}
if (index >= num / 2 || sum > num)
{
// Use to stop process
// 1) When sum is greater than num or
// 2) index is outside the limit
return;
}
for (int i = value; i <= num; ++i)
{
if (prime[i]==true)
{
// When i is prime
result[index] = i;
// Find next element
partition(i, prime, result, index + 1, sum + i, num);
}
}
}
public void primePartition(int num)
{
if (num <= 1)
{
return;
}
// This are collecting prime number
boolean[] prime = new boolean[num + 1];
// Use to collect result
int[] result = new int[num / 2];
// Find prime number
this.sieveOfEratosthenes(prime, num);
// Display given number
System.out.print("\n Given number : " + num );
// Find partition
this.partition(2, prime, result, 0, 0, num);
}
public static void main(String[] args)
{
Partitions task = new Partitions();
// Test
task.primePartition(7);
task.primePartition(17);
task.primePartition(9);
}
}``````

#### Output

`````` Given number : 7
2 2 3
2 5
7
Given number : 17
2 2 2 2 2 2 2 3
2 2 2 2 2 2 5
2 2 2 2 2 7
2 2 2 2 3 3 3
2 2 2 3 3 5
2 2 2 11
2 2 3 3 7
2 2 3 5 5
2 2 13
2 3 3 3 3 3
2 3 5 7
2 5 5 5
3 3 3 3 5
3 3 11
3 7 7
5 5 7
17
Given number : 9
2 2 2 3
2 2 5
2 7
3 3 3``````
``````// Include header file
#include <iostream>
using namespace std;
/*
C++ program
Generate all prime partition of a number
*/
class Partitions
{
public:
// Find all prime numbers which have smaller and equal to given number n
void sieveOfEratosthenes(bool prime[], int n)
{
// Initial two numbers are not prime (0 and 1)
prime[0] = false;
prime[1] = false;
// Set the initial (2 to n element is prime)
for (int i = 2; i <= n; ++i)
{
prime[i] = true;
}
// We start to 2
for (int i = 2; i * i <= n; ++i)
{
if (prime[i] == true)
{
// When i is prime number
// Modify the prime status of all
// next multiplier of location i
for (int j = i * i; j <= n; j += i)
{
prime[j] = false;
}
}
}
}
// Display calculated result
void printData(int result[], int size)
{
cout << "\n";
for (int i = 0; i < size; ++i)
{
cout << " " << result[i];
}
}
void partition(int value, bool prime[],
int result[], int index, int sum, int num)
{
if (sum == num)
{
// Print the result
this->printData(result, index);
return;
}
if (index >= num / 2 || sum > num)
{
// Use to stop process
// 1) When sum is greater than num or
// 2) index is outside the limit
return;
}
for (int i = value; i <= num; ++i)
{
if (prime[i] == true)
{
// When i is prime
result[index] = i;
// Find next element
this->partition(i, prime,
result, index + 1, sum + i, num);
}
}
}
void primePartition(int num)
{
if (num <= 1)
{
return;
}
// This are collecting prime number
bool prime[num + 1];
// Use to collect result
int result[num / 2];
// Find prime number
this->sieveOfEratosthenes(prime, num);
// Display given number
cout << "\n Given number : " << num;
// Find partition
this->partition(2, prime, result, 0, 0, num);
}
};
int main()
{
Partitions *task = new Partitions();
// Test
task->primePartition(7);
task->primePartition(17);
task->primePartition(9);
return 0;
}``````

#### Output

`````` Given number : 7
2 2 3
2 5
7
Given number : 17
2 2 2 2 2 2 2 3
2 2 2 2 2 2 5
2 2 2 2 2 7
2 2 2 2 3 3 3
2 2 2 3 3 5
2 2 2 11
2 2 3 3 7
2 2 3 5 5
2 2 13
2 3 3 3 3 3
2 3 5 7
2 5 5 5
3 3 3 3 5
3 3 11
3 7 7
5 5 7
17
Given number : 9
2 2 2 3
2 2 5
2 7
3 3 3``````
``````// Include namespace system
using System;
/*
Csharp program
Generate all prime partition of a number
*/
public class Partitions
{
// Find all prime numbers which have smaller and equal to given number n
public void sieveOfEratosthenes(Boolean[] prime, int n)
{
// Initial two numbers are not prime (0 and 1)
prime[0] = false;
prime[1] = false;
// Set the initial (2 to n element is prime)
for (int i = 2; i <= n; ++i)
{
prime[i] = true;
}
// We start to 2
for (int i = 2; i * i <= n; ++i)
{
if (prime[i] == true)
{
// When i is prime number
// Modify the prime status of all next multiplier of location i
for (int j = i * i; j <= n; j += i)
{
prime[j] = false;
}
}
}
}
// Display calculated result
public void printData(int[] result, int size)
{
Console.Write("\n");
for (int i = 0; i < size; ++i)
{
Console.Write(" " + result[i]);
}
}
public void partition(int value, Boolean[] prime, int[] result, int index, int sum, int num)
{
if (sum == num)
{
// Print the result
this.printData(result, index);
return;
}
if (index >= num / 2 || sum > num)
{
// Use to stop process
// 1) When sum is greater than num or
// 2) index is outside the limit
return;
}
for (int i = value; i <= num; ++i)
{
if (prime[i] == true)
{
// When i is prime
result[index] = i;
// Find next element
this.partition(i, prime, result, index + 1, sum + i, num);
}
}
}
public void primePartition(int num)
{
if (num <= 1)
{
return;
}
// This are collecting prime number
Boolean[] prime = new Boolean[num + 1];
// Use to collect result
int[] result = new int[num / 2];
// Find prime number
this.sieveOfEratosthenes(prime, num);
// Display given number
Console.Write("\n Given number : " + num);
// Find partition
this.partition(2, prime, result, 0, 0, num);
}
public static void Main(String[] args)
{
Partitions task = new Partitions();
// Test
task.primePartition(7);
task.primePartition(17);
task.primePartition(9);
}
}``````

#### Output

`````` Given number : 7
2 2 3
2 5
7
Given number : 17
2 2 2 2 2 2 2 3
2 2 2 2 2 2 5
2 2 2 2 2 7
2 2 2 2 3 3 3
2 2 2 3 3 5
2 2 2 11
2 2 3 3 7
2 2 3 5 5
2 2 13
2 3 3 3 3 3
2 3 5 7
2 5 5 5
3 3 3 3 5
3 3 11
3 7 7
5 5 7
17
Given number : 9
2 2 2 3
2 2 5
2 7
3 3 3``````
``````package main
import "fmt"
/*
Go program
Generate all prime partition of a number
*/
type Partitions struct {}
func getPartitions() * Partitions {
var me *Partitions = &Partitions {}
return me
}
// Find all prime numbers which have smaller and equal to given number n
func(this Partitions) sieveOfEratosthenes(prime[] bool, n int) {
// Initial two numbers are not prime (0 and 1)
prime[0] = false
prime[1] = false
// We start to 2
for i := 2 ; i * i <= n ; i++ {
if prime[i] == true {
// When i is prime number
// Modify the prime status of all next multiplier of location i
for j := i * i ; j <= n ; j += i {
prime[j] = false
}
}
}
}
// Display calculated result
func(this Partitions) printData(result[] int, size int) {
fmt.Print("\n")
for i := 0 ; i < size ; i++ {
fmt.Print(" ", result[i])
}
}
func(this Partitions) partition(value int, prime[] bool,
result[] int, index int, sum int, num int) {
if sum == num {
// Print the result
this.printData(result, index)
return
}
if index >= num / 2 || sum > num {
// Use to stop process
// 1) When sum is greater than num or
// 2) index is outside the limit
return
}
for i := value ; i <= num ; i++ {
if prime[i] == true {
// When i is prime
result[index] = i
// Find next element
this.partition(i, prime, result, index + 1, sum + i, num)
}
}
}
func(this Partitions) primePartition(num int) {
if num <= 1 {
return
}
// This are collecting prime number
// Set the initial (2 to n element is prime)
var prime = make([] bool, num + 1)
for i := 0; i <= num; i++ {
prime[i] = true
}
// Use to collect result
var result = make([] int, num / 2)

// Find prime number
this.sieveOfEratosthenes(prime, num)
// Display given number
fmt.Print("\n Given number : ", num)
// Find partition
this.partition(2, prime, result, 0, 0, num)
}
func main() {
var task * Partitions = getPartitions()
// Test
task.primePartition(7)
task.primePartition(17)
task.primePartition(9)
}``````

#### Output

`````` Given number : 7
2 2 3
2 5
7
Given number : 17
2 2 2 2 2 2 2 3
2 2 2 2 2 2 5
2 2 2 2 2 7
2 2 2 2 3 3 3
2 2 2 3 3 5
2 2 2 11
2 2 3 3 7
2 2 3 5 5
2 2 13
2 3 3 3 3 3
2 3 5 7
2 5 5 5
3 3 3 3 5
3 3 11
3 7 7
5 5 7
17
Given number : 9
2 2 2 3
2 2 5
2 7
3 3 3``````
``````<?php
/*
Php program
Generate all prime partition of a number
*/
class Partitions
{
// Find all prime numbers which have smaller and equal to given number n
public	function sieveOfEratosthenes(&\$prime, \$n)
{
// Initial two numbers are not prime (0 and 1)
\$prime[0] = false;
\$prime[1] = false;
// We start to 2
for (\$i = 2; \$i * \$i <= \$n; ++\$i)
{
if (\$prime[\$i] == true)
{
// When i is prime number
// Modify the prime status of all next multiplier of location i
for (\$j = \$i * \$i; \$j <= \$n; \$j += \$i)
{
\$prime[\$j] = false;
}
}
}
}
// Display calculated result
public	function printData(\$result, \$size)
{
echo("\n");
for (\$i = 0; \$i < \$size; ++\$i)
{
echo(" ".\$result[\$i]);
}
}
public	function partition(\$value, \$prime,
\$result, \$index,
\$sum, \$num)
{
if (\$sum == \$num)
{
// Print the result
\$this->printData(\$result, \$index);
return;
}
if (\$index >= (int)(\$num / 2) || \$sum > \$num)
{
// Use to stop process
// 1) When sum is greater than num or
// 2) index is outside the limit
return;
}
for (\$i = \$value; \$i <= \$num; ++\$i)
{
if (\$prime[\$i] == true)
{
// When i is prime
\$result[\$index] = \$i;
// Find next element
\$this->partition(\$i, \$prime, \$result,
\$index + 1,
\$sum + \$i, \$num);
}
}
}
public	function primePartition(\$num)
{
if (\$num <= 1)
{
return;
}
// This are collecting prime number
// Set the initial (2 to n element is prime)
\$prime = array_fill(0, \$num + 1, true);
// Use to collect result
\$result = array_fill(0, (int)(\$num / 2), 0);
// Find prime number
\$this->sieveOfEratosthenes(\$prime, \$num);
// Display given number
echo("\n Given number : ".\$num);
// Find partition
\$this->partition(2, \$prime, \$result, 0, 0, \$num);
}
}

function main()
{
\$task = new Partitions();
// Test
\$task->primePartition(7);
\$task->primePartition(17);
\$task->primePartition(9);
}
main();``````

#### Output

`````` Given number : 7
2 2 3
2 5
7
Given number : 17
2 2 2 2 2 2 2 3
2 2 2 2 2 2 5
2 2 2 2 2 7
2 2 2 2 3 3 3
2 2 2 3 3 5
2 2 2 11
2 2 3 3 7
2 2 3 5 5
2 2 13
2 3 3 3 3 3
2 3 5 7
2 5 5 5
3 3 3 3 5
3 3 11
3 7 7
5 5 7
17
Given number : 9
2 2 2 3
2 2 5
2 7
3 3 3``````
``````/*
Node JS program
Generate all prime partition of a number
*/
class Partitions
{
// Find all prime numbers which have smaller and equal to given number n
sieveOfEratosthenes(prime, n)
{
// Initial two numbers are not prime (0 and 1)
prime[0] = false;
prime[1] = false;
// We start to 2
for (var i = 2; i * i <= n; ++i)
{
if (prime[i] == true)
{
// When i is prime number
// Modify the prime status of all next multiplier of location i
for (var j = i * i; j <= n; j += i)
{
prime[j] = false;
}
}
}
}
// Display calculated result
printData(result, size)
{
process.stdout.write("\n");
for (var i = 0; i < size; ++i)
{
process.stdout.write(" " + result[i]);
}
}
partition(value, prime, result, index, sum, num)
{
if (sum == num)
{
// Print the result
this.printData(result, index);
return;
}
if (index >= parseInt(num / 2) || sum > num)
{
// Use to stop process
// 1) When sum is greater than num or
// 2) index is outside the limit
return;
}
for (var i = value; i <= num; ++i)
{
if (prime[i] == true)
{
// When i is prime
result[index] = i;
// Find next element
this.partition(i, prime, result,
index + 1, sum + i, num);
}
}
}
primePartition(num)
{
if (num <= 1)
{
return;
}
// This are collecting prime number
// Set the initial (2 to n element is prime)
var prime = Array(num + 1).fill(true);
// Use to collect result
var result = Array(parseInt(num / 2)).fill(0);
// Find prime number
this.sieveOfEratosthenes(prime, num);
// Display given number
process.stdout.write("\n Given number : " + num);
// Find partition
this.partition(2, prime, result, 0, 0, num);
}
}

function main()
{
var task = new Partitions();
// Test
task.primePartition(7);
task.primePartition(17);
task.primePartition(9);
}
main();``````

#### Output

`````` Given number : 7
2 2 3
2 5
7
Given number : 17
2 2 2 2 2 2 2 3
2 2 2 2 2 2 5
2 2 2 2 2 7
2 2 2 2 3 3 3
2 2 2 3 3 5
2 2 2 11
2 2 3 3 7
2 2 3 5 5
2 2 13
2 3 3 3 3 3
2 3 5 7
2 5 5 5
3 3 3 3 5
3 3 11
3 7 7
5 5 7
17
Given number : 9
2 2 2 3
2 2 5
2 7
3 3 3``````
``````#    Python 3 program
#    Generate all prime partition of a number
class Partitions :
#  Find all prime numbers which have smaller and equal to given number n
def sieveOfEratosthenes(self, prime, n) :
#  Initial two numbers are not prime (0 and 1)
prime[0] = False
prime[1] = False
i = 2
#  We start to 2
while (i * i <= n) :
if (prime[i] == True) :
j = i * i
#  When i is prime number
#  Modify the prime status of all next multiplier of location i
while (j <= n) :
prime[j] = False
j += i

i += 1

#  Display calculated result
def printData(self, result, size) :
print(end = "\n")
i = 0
while (i < size) :
print(" ", result[i], end = "")
i += 1

def partition(self, value, prime, result, index, sum, num) :
if (sum == num) :
#  Print the result
self.printData(result, index)
return

if (index >= int(num / 2) or sum > num) :
#  Use to stop process
#  1) When sum is greater than num or
#  2) index is outside the limit
return

i = value
while (i <= num) :
if (prime[i] == True) :
#  When i is prime
result[index] = i
#  Find next element
self.partition(i, prime, result, index + 1, sum + i, num)

i += 1

def primePartition(self, num) :
if (num <= 1) :
return

#  This are collecting prime number
#  Set the initial (2 to n element is prime)
prime = [True] * (num + 1)
#  Use to collect result
result = [0] * (int(num / 2))
#  Find prime number
self.sieveOfEratosthenes(prime, num)
#  Display given number
print("\n Given number : ", num, end = "")
#  Find partition
self.partition(2, prime, result, 0, 0, num)

def main() :
task = Partitions()
#  Test
task.primePartition(7)
task.primePartition(17)
task.primePartition(9)

if __name__ == "__main__": main()``````

#### Output

`````` Given number :  7
2  2  3
2  5
7
Given number :  17
2  2  2  2  2  2  2  3
2  2  2  2  2  2  5
2  2  2  2  2  7
2  2  2  2  3  3  3
2  2  2  3  3  5
2  2  2  11
2  2  3  3  7
2  2  3  5  5
2  2  13
2  3  3  3  3  3
2  3  5  7
2  5  5  5
3  3  3  3  5
3  3  11
3  7  7
5  5  7
17
Given number :  9
2  2  2  3
2  2  5
2  7
3  3  3``````
``````#    Ruby program
#    Generate all prime partition of a number
class Partitions
#  Find all prime numbers which have smaller and equal to given number n
def sieveOfEratosthenes(prime, n)
#  Initial two numbers are not prime (0 and 1)
prime[0] = false
prime[1] = false
i = 2
#  We start to 2
while (i * i <= n)
if (prime[i] == true)
j = i * i
#  When i is prime number
#  Modify the prime status of all next multiplier of location i
while (j <= n)
prime[j] = false
j += i
end

end

i += 1
end

end

#  Display calculated result
def printData(result, size)
print("\n")
i = 0
while (i < size)
print(" ", result[i])
i += 1
end

end

def partition(value, prime, result, index, sum, num)
if (sum == num)
#  Print the result
self.printData(result, index)
return
end

if (index >= num / 2 || sum > num)
#  Use to stop process
#  1) When sum is greater than num or
#  2) index is outside the limit
return
end

i = value
while (i <= num)
if (prime[i] == true)
#  When i is prime
result[index] = i
#  Find next element
self.partition(i, prime, result, index + 1, sum + i, num)
end

i += 1
end

end

def primePartition(num)
if (num <= 1)
return
end

#  This are collecting prime number
#  Set the initial (2 to n element is prime)
prime = Array.new(num + 1) {true}
#  Use to collect result
result = Array.new(num / 2) {0}
#  Find prime number
self.sieveOfEratosthenes(prime, num)
#  Display given number
print("\n Given number : ", num)
#  Find partition
self.partition(2, prime, result, 0, 0, num)
end

end

def main()
task = Partitions.new()
#  Test
task.primePartition(7)
task.primePartition(17)
task.primePartition(9)
end

main()``````

#### Output

`````` Given number : 7
2 2 3
2 5
7
Given number : 17
2 2 2 2 2 2 2 3
2 2 2 2 2 2 5
2 2 2 2 2 7
2 2 2 2 3 3 3
2 2 2 3 3 5
2 2 2 11
2 2 3 3 7
2 2 3 5 5
2 2 13
2 3 3 3 3 3
2 3 5 7
2 5 5 5
3 3 3 3 5
3 3 11
3 7 7
5 5 7
17
Given number : 9
2 2 2 3
2 2 5
2 7
3 3 3``````
``````/*
Scala program
Generate all prime partition of a number
*/
class Partitions()
{
// Find all prime numbers which have smaller and equal to given number n
def sieveOfEratosthenes(prime: Array[Boolean], n: Int): Unit = {
// Initial two numbers are not prime (0 and 1)
prime(0) = false;
prime(1) = false;
var i: Int = 2;
// We start to 2
while (i * i <= n)
{
if (prime(i) == true)
{
var j: Int = i * i;
// When i is prime number
// Modify the prime status of all next multiplier of location i
while (j <= n)
{
prime(j) = false;
j += i;
}
}
i += 1;
}
}
// Display calculated result
def printData(result: Array[Int], size: Int): Unit = {
print("\n");
var i: Int = 0;
while (i < size)
{
print(" " + result(i));
i += 1;
}
}
def partition(value: Int, prime: Array[Boolean],
result: Array[Int], index: Int, sum: Int, num: Int): Unit = {
if (sum == num)
{
// Print the result
printData(result, index);
return;
}
if (index >= num / 2 || sum > num)
{
// Use to stop process
// 1) When sum is greater than num or
// 2) index is outside the limit
return;
}
var i: Int = value;
while (i <= num)
{
if (prime(i) == true)
{
// When i is prime
result(index) = i;
// Find next element
partition(i, prime, result, index + 1, sum + i, num);
}
i += 1;
}
}
def primePartition(num: Int): Unit = {
if (num <= 1)
{
return;
}
// This are collecting prime number
// Set the initial (2 to n element is prime)
var prime: Array[Boolean] = Array.fill[Boolean](num + 1)(true);
// Use to collect result
var result: Array[Int] = Array.fill[Int](num / 2)(0);
// Find prime number
this.sieveOfEratosthenes(prime, num);
// Display given number
print("\n Given number : " + num);
// Find partition
this.partition(2, prime, result, 0, 0, num);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Partitions = new Partitions();
// Test
task.primePartition(7);
task.primePartition(17);
task.primePartition(9);
}
}``````

#### Output

`````` Given number : 7
2 2 3
2 5
7
Given number : 17
2 2 2 2 2 2 2 3
2 2 2 2 2 2 5
2 2 2 2 2 7
2 2 2 2 3 3 3
2 2 2 3 3 5
2 2 2 11
2 2 3 3 7
2 2 3 5 5
2 2 13
2 3 3 3 3 3
2 3 5 7
2 5 5 5
3 3 3 3 5
3 3 11
3 7 7
5 5 7
17
Given number : 9
2 2 2 3
2 2 5
2 7
3 3 3``````
``````/*
Swift 4 program
Generate all prime partition of a number
*/
class Partitions
{
// Find all prime numbers which have smaller and equal to given number n
func sieveOfEratosthenes(_ prime: inout[Bool], _ n: Int)
{
// Initial two numbers are not prime (0 and 1)
prime[0] = false;
prime[1] = false;
var i: Int = 2;
// We start to 2
while (i * i <= n)
{
if (prime[i] == true)
{
var j: Int = i * i;
// When i is prime number
// Modify the prime status of all next multiplier of location i
while (j <= n)
{
prime[j] = false;
j += i;
}
}
i += 1;
}
}
// Display calculated result
func printData(_ result: [Int], _ size: Int)
{
print(terminator: "\n");
var i: Int = 0;
while (i < size)
{
print(" ", result[i], terminator: "");
i += 1;
}
}
func partition(_ value: Int, _ prime: [Bool],
_ result: inout[Int], _ index: Int, _ sum: Int, _ num: Int)
{
if (sum == num)
{
// Print the result
self.printData(result, index);
return;
}
if (index >= num / 2 || sum > num)
{
// Use to stop process
// 1) When sum is greater than num or
// 2) index is outside the limit
return;
}
var i: Int = value;
while (i <= num)
{
if (prime[i] == true)
{
// When i is prime
result[index] = i;
// Find next element
self.partition(i, prime, &result,
index + 1, sum + i, num);
}
i += 1;
}
}
func primePartition(_ num: Int)
{
if (num <= 1)
{
return;
}
// This are collecting prime number
// Set the initial (2 to n element is prime)
var prime: [Bool] = Array(repeating: true, count: num + 1);
// Use to collect result
var result: [Int] = Array(repeating: 0, count: num / 2);
// Find prime number
self.sieveOfEratosthenes(&prime, num);
// Display given number
print("\n Given number : ", num, terminator: "");
// Find partition
self.partition(2, prime, &result, 0, 0, num);
}
}
func main()
{
let task: Partitions = Partitions();
// Test
task.primePartition(7);
task.primePartition(17);
task.primePartition(9);
}
main();``````

#### Output

`````` Given number :  7
2  2  3
2  5
7
Given number :  17
2  2  2  2  2  2  2  3
2  2  2  2  2  2  5
2  2  2  2  2  7
2  2  2  2  3  3  3
2  2  2  3  3  5
2  2  2  11
2  2  3  3  7
2  2  3  5  5
2  2  13
2  3  3  3  3  3
2  3  5  7
2  5  5  5
3  3  3  3  5
3  3  11
3  7  7
5  5  7
17
Given number :  9
2  2  2  3
2  2  5
2  7
3  3  3``````
``````/*
Kotlin program
Generate all prime partition of a number
*/
class Partitions
{
// Find all prime numbers which have smaller and equal to given number n
fun sieveOfEratosthenes(prime: Array < Boolean > , n: Int): Unit
{
// Initial two numbers are not prime (0 and 1)
prime[0] = false;
prime[1] = false;
var i: Int = 2;
// We start to 2
while (i * i <= n)
{
if (prime[i] == true)
{
var j: Int = i * i;
// When i is prime number
// Modify the prime status of all next multiplier of location i
while (j <= n)
{
prime[j] = false;
j += i;
}
}
i += 1;
}
}
// Display calculated result
fun printData(result: Array < Int > , size: Int): Unit
{
print("\n");
var i: Int = 0;
while (i < size)
{
print(" " + result[i]);
i += 1;
}
}
fun partition(value: Int, prime: Array < Boolean > ,
result: Array < Int > , index: Int, sum: Int, num: Int): Unit
{
if (sum == num)
{
// Print the result
this.printData(result, index);
return;
}
if (index >= num / 2 || sum > num)
{
// Use to stop process
// 1) When sum is greater than num or
// 2) index is outside the limit
return;
}
var i: Int = value;
while (i <= num)
{
if (prime[i] == true)
{
// When i is prime
result[index] = i;
// Find next element
this.partition(i, prime, result, index + 1, sum + i, num);
}
i += 1;
}
}
fun primePartition(num: Int): Unit
{
if (num <= 1)
{
return;
}
// This are collecting prime number
// Set the initial (2 to n element is prime)
val prime: Array < Boolean > = Array(num + 1)
{
true
};
// Use to collect result
val result: Array < Int > = Array(num / 2)
{
0
};
// Find prime number
this.sieveOfEratosthenes(prime, num);
// Display given number
print("\n Given number : " + num);
// Find partition
this.partition(2, prime, result, 0, 0, num);
}
}
fun main(args: Array < String > ): Unit
{
val task: Partitions = Partitions();
// Test
task.primePartition(7);
task.primePartition(17);
task.primePartition(9);
}``````

#### Output

`````` Given number : 7
2 2 3
2 5
7
Given number : 17
2 2 2 2 2 2 2 3
2 2 2 2 2 2 5
2 2 2 2 2 7
2 2 2 2 3 3 3
2 2 2 3 3 5
2 2 2 11
2 2 3 3 7
2 2 3 5 5
2 2 13
2 3 3 3 3 3
2 3 5 7
2 5 5 5
3 3 3 3 5
3 3 11
3 7 7
5 5 7
17
Given number : 9
2 2 2 3
2 2 5
2 7
3 3 3``````

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

### New Comment

Kalkicodeteam     494 Day ago
``````Sorry to late response.
How can you do that by printing the result in reverse order. For example
==========================
// Display calculated result
void printData(int result[], int size)
{
printf("\n");
for (int i = size-1; i >= 0; --i)
{
printf(" %d", result[i]);
}
}
======================
You can do by replace this method.``````
Dominik     524 Day ago
``````How to display those numbers in opposite direction? I mean instead of 2 2 3 i would like to have 3 2 2.
I tried to sort this result array before displaying it but in some cases this has changed the array.
Thank You in advance``````