Saturday, April 6, 2013

Subsets such that the sum of numbers in the subset is a prime number.

Given a set of numbers [1-N] . Find the number of subsets such that the sum of numbers in the subset is a prime number.

Algorithm :

1) Generate all subsets using 0-1 Knapsack i.e this helps determine the number of ways it is possible get the value i, input ranging from 1 to n. The general complexity of 0-1 Knapsack is O(nK) where K is the sum of all elements in the vector. Since there are numbers ranging from 1 to n i.e sum is n(n-1)/2. The overall complexity becomes O(n^3)

For each number in the Sum S, check if there is subset of numbers from 1 to N that sum up to S - Yes that you can do with Subset Sum problem. Recurrence for the same is:
Sum[0,0]=True
For S=1 to L do Sum[0, S]= False
For k=1 to n do
     For S = 0 to L do
           Sum[k, S] = Sum[k-1, S] or Sum[k-1, S - x(k)]

2) Iterate all subsets which are prime. O(K)

public class PrimeSubset {

private static int[] primes;
private static int count = 0;

public static void main(String[] args) {
findPrimeSubsets(100);
}

public static void findPrimeSubsets(int N) {
int sum = (N * (N + 1)) / 2;
primes = new int[sum];
primes[0] = 2;
primes[1] = 3;
count = 2;

boolean[][] matrix = new boolean[N + 1][sum + 1];

for (int i = 0; i <= N; i++) {
matrix[i][0] = true;
}

for (int j = 1; j <= sum; j++) {
matrix[0][j] = false;
}

for (int i = 1; i <= N; i++) {
for (int j = 1; j <= sum; j++) {
matrix[i][j] = matrix[i - 1][j]
|| ((i <= j) && (matrix[i - 1][j - i]));
}
}

for (int i = 2; i <= sum; i++) {
if (matrix[N][i] && isPrime(i)) {
System.out.println(i);
primes[count] = i;
++count;
}
}
}

public static boolean isPrime(int n) {

if (n <= 1) {
return false;
} else if (n == 2 || n == 3) {
return true;
}
int sqrt = (int) Math.ceil(Math.sqrt(n));
boolean prime = true;
for (int k = 0; k < count && primes[k] <= sqrt; k++) {
if (n % primes[k] == 0) {
prime = false;
break;
}
}
return prime;
}
}

No comments: