Ronzii's Blog

Just your average geek's blog

Prime Subsets

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 prime numbers using sieve of eratosthenes (O(n^2))
  2. 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)
  3. Iterate all subsets which are prime. O(K)
#include <iostream>
#include <bitset>
#include <vector>
#include <algorithm>
#define SIZE 1000
#define MAX (int)(SIZE-3)/2
using namespace std;
unsigned long long primes[MAX+1];
bitset<MAX+1> bset;
void setPrimes()
{
    unsigned long long i,j;
    for(i=0; i*i<=SIZE; i++)
        if(!bset.test(i))
            for(j=i+1; (2*j+1)*(2*i+3)<=SIZE; j++)
                bset.set(((2*j+1)*(2*i+3)-3)/2);
    primes[0]=2;
    for(i=1,j=0; j<MAX+1; j++)
        if(!bset.test(j))
            primes[i++]=2*j+3;
}
int knapsack(int n)
{
    vector<int> v;
    for(int i=1; i<=n; i++)
        v.push_back(i);
    int sum = accumulate(v.begin(),v.end(),0);
    int *s = new int[sum];
    for(int i=0; i<sum; i++) s[i] = 0;
    s[0] = 1;
    for(int i=0; i<v.size(); i++)
    {
        for(int j = sum-v[i]; j>=0; j--)
        {
            if(s[j])
            {
                s[j+v[i]]+=1;
            }
        }
    }
    int total = 0;
    for(int i=0; i<n; i++)
    {
        cout<<primes[i]<<" "<<s[primes[i]]<<endl;
        total+=s[primes[i]];
    }
    return total;
}
int main()
{
    setPrimes();
    cout<<knapsack(10);
    return 0;
}

March 26, 2012 Posted by | C++, Dynamic Programming | , , , , , | 2 Comments