Go4Expert - View Single Post - Generating prime set which add upto particular number

SaswatPadhi

I had changed (improved the performance of) the above code but had forgotten to post it here.
When I saw this threads' name in the recent threads list, I remembered to post it.

Here it is, the new code :

Code: CPP

#include <cmath>
#include <ctime>
#include <vector>
#include <fstream>
#include <iostream>
#include <algorithm>

using namespace std;

#define VectorList vector< vector<int> >

#define MINI_OUTPUT
#define MEGA_OUTPUT
//#define ASC_ORDERED
//#define FILE_OUTPUT
#define TIME_CALC

#define MaxLimit 600

VectorList MyList;
int Primes[200];
int LastIndex;
vector<int> TList;
#ifdef FILE_OUTPUT
    ofstream fout;
#endif

void PrimeGen();
int RPS(int,int,int,int);
int BS(int,int,int);
void PrintVector(vector<int>);
#ifdef FILE_OUTPUT
    void PrintFVector(vector<int>);
#endif
bool VectorCompare(vector<int>,vector<int>);

int main()
{
    PrimeGen();
    int TOTAL, Found, UserInput, Parts;
    UserInput = 0;
    TList.clear();

    #ifdef FILE_OUTPUT
        fout.open("C:\\MyList.txt");
    #endif

    while ( ( UserInput < 1 ) || ( UserInput > MaxLimit ) )
    {
        cout << "(*) Enter the number (<= " << MaxLimit << "): ";
        cin >> UserInput;
        #ifdef FILE_OUTPUT
            fout << "(*) Enter the number (<= " << MaxLimit << "): " << UserInput << endl;
        #endif
    }

    #ifdef TIME_CALC
        clock_t t1, t2;
        t1 = clock();
    #endif
    LastIndex = 23+(UserInput/log(UserInput));
    TOTAL = 0;
    for (Parts=1; Parts <= sqrt(UserInput); ++Parts)
    {
        MyList.clear();
        Found = RPS(UserInput,Parts,0,0);

        if (++Found)
        {
            #ifdef ASC_ORDERED
                for (int i=0; i<Found; ++i)
                    sort(MyList[i].begin(), MyList[i].end());
            #endif

            Found = MyList.end()-MyList.begin();

            #ifdef MINI_OUTPUT
                cout << "\n(~) Found " << Found << " ways of expressing " << UserInput << " as a sum of " << Parts << " primes.";
                #ifdef FILE_OUTPUT
                    fout << "\n(~) Found " << Found << " ways of expressing " << UserInput << " as a sum of " << Parts << " primes.";
                #endif
                #ifdef MEGA_OUTPUT
                    for (int i=0; i<Found; ++i)
                    {
                        cout << "\n--> ";
                        PrintVector(MyList[i]);
                        #ifdef FILE_OUTPUT
                            fout << "\n--> ";
                            PrintFVector(MyList[i]);
                        #endif
                    }
                    cout << endl;
                #endif
            #endif
            TOTAL += Found;
        }
    }
    cout << "\n\n----< TOTAL " << TOTAL << " UNIQUE SETS OF PRIMES FOUND, WHICH ADD TO " << UserInput << ". >----\n";
    #ifdef FILE_OUTPUT
        fout << "\n\n----< TOTAL " << TOTAL << " UNIQUE SETS OF PRIMES FOUND, WHICH ADD TO " << UserInput << ". >----\n";
    #endif
    #ifdef TIME_CALC
        t2 = clock();
        cout << "\n----< TIME OF EXECUTION = " << ((float)t2 - (float)t1)/1000.0F <<" sec. >----\n";
        #ifdef FILE_OUTPUT
            fout << "\n----< TIME OF EXECUTION = " << ((float)t2 - (float)t1)/1000.0F <<" sec. >----\n";
        #endif
    #endif
    #ifdef FILE_OUTPUT
        fout.close();
    #endif
    return 0;
}

void PrimeGen()
{
    int flag, Cntr=0;
    Primes[0] = 2;
    for (int i=3; i < MaxLimit+1; ++i)
    {
        flag=0;
        for (int j=2; j <= sqrt(i); ++j)
        {
            if ( ! (i%j) )
            {
                flag=-1;
                break;
            }
        }
        if (!flag)
            Primes[++Cntr]=i;
    }
    LastIndex = Cntr;
}

int BS(int first, int last, int key)
{
    while (first <= last)
    {
        int mid = (first + last) / 2;
        if (key > Primes[mid])
            first = mid + 1;
        else if (key < Primes[mid])
            last = mid - 1;
        else
            return 0;
    }
    return -1;
}

void PrintVector( vector<int> MyVector )
{
    int i, j = MyVector.size();
    cout << " { ";
    for (i=0; i<j-1; ++i)
        cout << MyVector[i] << ", ";
    cout << MyVector[i] << " }";
}

#ifdef FILE_OUTPUT
    void PrintFVector( vector<int> MyVector )
    {
        int i, j = MyVector.size();
        fout << " { ";
        for (i=0; i<j-1; ++i)
            fout << MyVector[i] << ", ";
        fout << MyVector[i] << " }";
    }
#endif

bool VectorCompare( vector<int> i, vector<int> j)
{
    return equal(i.begin(), i.end(), j.begin());
}

int RPS(int n, int k, int MIndex, int PStart)
{
    int R, BMI = MIndex+1;
    if (k==1)
    {
        if ( BS(PStart,LastIndex,n) )
            return -1;
        else
        {
            if( MyList.size() <= MIndex )
                MyList.push_back(TList);
            MyList[MIndex].push_back(n);
            return 0;
        }
    }
    else
    {
        for (int i=PStart; Primes[i]<= n/k; ++i)
        {
            R = RPS(n-Primes[i], k-1, MIndex,i+1);
            if ( R != -1)
            {
                for (int j=0; j <= R; ++j)
                {
                    if( MyList.size() <= MIndex )
                        MyList.push_back(TList);
                    MyList[MIndex].push_back(Primes[i]);
                    ++MIndex;
                }
            }
        }
        return MIndex-BMI;
    }
}

If you notice closely, there isn't much change in the code.
Actually, what I had done earlier was, I was checking all vectors (which were the prime-sets) for their possible duplicates.
But I just noticed (few days after posting the article here) that the way I generate the primes-sets, all of them must be unique. And they actually were !
So, I just removed the duplicate check :

Code: C++

Found = unique(MyList.begin(), MyList.end(), VectorCompare)-MyList.begin();

to :

Code: C++

Found = MyList.end()-MyList.begin();

And, you get a 20% performance improvement.

[[ I request shabbir to replace the code in the article with the one above. ]]