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

Project Euler Problem 7

#include <iostream>
#include <bitset>
#define SIZE 1000000
#define MAX (int)(SIZE-3)/2
using namespace std;
unsigned long long primes[MAX+1];    //array that stores the primes up to sqrt(SIZE)
bitset<MAX+1> bset;   //auxiliary bitset used to make the sieve
void setPrimes()
{
    unsigned long long i,j;
    for(i=0; i*i<=SIZE; i++)   //we only have to get primes up to sqrt(SIZE)
        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);   //setting all non-primes
    primes[0]=2;                                   //store the first prime (that is 2)
    for(i=1,j=0; j<MAX+1; j++)
        if(!bset.test(j))
            primes[i++]=2*j+3;                     //store the remaining odd primes
}
int main()
{
    setPrimes();
    cout<<primes[10000];
    return 0;
}

March 21, 2012 Posted by | C++ | , , , | Leave a comment

Project Euler Problem 3

#include <iostream>
#include <bitset>
#define SIZE 1000000
#define MAX (int)(SIZE-3)/2
using namespace std;
unsigned long long primes[MAX+1];    //array that stores the primes up to sqrt(SIZE)
bitset<MAX+1> bset;   //auxiliary bitset used to make the sieve
void setPrimes()
{
    unsigned long long i,j;
    for(i=0; i*i<=SIZE; i++)   //we only have to get primes up to sqrt(SIZE)
        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);   //setting all non-primes
    primes[0]=2;                                   //store the first prime (that is 2)
    for(i=1,j=0; j<MAX+1; j++)
        if(!bset.test(j))
            primes[i++]=2*j+3;                     //store the remaining odd primes
}
int main()
{
    setPrimes();
    unsigned long long N = 600851475143,i=30000;
    while(1)
    {
        if(N%primes[i]==0)
        {
            cout<<primes[i]<<endl;
            break;
        }
        i--;
    }
    return 0;
}

March 21, 2012 Posted by | C++ | , , , , , | Leave a comment

Miller-Rabin Primality Test

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
long long mulmod(long long a, long long b , long long c)
{
    long long x=0,y=a%c;
    while(b>0)
    {
        if(b & 1)
        {
            x = (x+y)%c;
        }
        y=(y*2)%c;
        b>>=1;
    }
    return x%c;
}
long long modulo(long long a,long long b,long long c)
{
    long long y=a,x=1;
    while(b>0)
    {
        if(b & 1)
        {
            x = mulmod(x,y,c);
        }
        y = mulmod(y,y,c);
        b>>=1;
    }
    return x%c;
}
bool miller(long long p,int iterations)
{
    if(p<2) return false;
    if(p!=2 && p%2==0) return false;
    long long s = p-1;
    while(s%2==0)
    {
        s/=2;
    }
    //printf("%lld\n",s);
    for(int i=0; i<iterations; i++)
    {
        long long a = rand()%(p-1)+1,temp=s;
        long long mod = modulo(a,temp,p);
        //printf("%lld %lld %lld %lld\n",a,temp,p,mod);
        while(temp!=p-1 && mod!=1 && mod!=p-1)
        {
            mod = mulmod(mod,mod,p);
            temp*=2;
            //printf("%lld %lld\n",temp,mod);
        }
        if(mod!=p-1 && temp%2==0)
        {
            return false;
        }

    }
    return true;
}
int main()
{
    long long a,b,c;
    while(scanf("%lld",&a))
    {
        if(miller(a,2)) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

March 4, 2012 Posted by | C++ | , , , , | Leave a comment

Optimal computation of a*b%c

long long mulmod(long long a,long long b,long long c)
{
    long long x = 0,y=a%c;
    while(b > 0)
    {
        if(b%2 == 1)
        {
            x = (x+y)%c;
        }
        y = (y*2)%c;
        b /= 2;
    }
    return x%c;
}

Read more at Topcoder

March 4, 2012 Posted by | C++ | , , , | Leave a comment