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:

Post a Comment