Skip to main content

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
Last updated on by Kalkicode




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