My Weblog

Blog about programming and math

Project Euler Problem 204

Project euler problem 204 solution is almost similar to Problem 293. I was going through the forum of project euler problem 293 where somebody mentioned this problem. Nothing fascinating except a bit of dynamic programming. c++ code.

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include<gmpxx.h>
typedef mpz_class _int;
using namespace std;
vector<_int> V[30],P;

void isprime()
	{
		bool b[100];
		memset(b,0,sizeof b);
		for(int i=2;i*i<100;i++) if(!b[i]) for(int j=i*i;j<100;j+=i)b[j]=1;
		for(int i=2;i<100;i++) if(!b[i])P.push_back(i);
		//for(int i=0;i<P.size();i++) cout<<P[i]<<" ";cout<<endl;
		//cout<<P.size();cout<<endl;

	}

int main()
	{
		isprime();
		int n=P.size();
		_int Lim=1;
		for(int i=1;i<=9;i++) Lim*=10;
		
		_int ret=1;
		V[0].push_back(1);
		while(1) { ret=ret*P[0]; if(ret>Lim) break; V[0].push_back(ret);}
		sort(V[0].begin(),V[0].end());
		_int tmp,sum=0;
		sum+=V[0].size();
		for(int i=1;i<P.size();i++) 
		{
			ret=1;
			while(1)
			{	
				ret=ret*P[i];
				if(ret>Lim) break;
				for(int j=0;j<i;j++) //calculate from 0 to previous 
				{
					for(int k=0;k<V[j].size();k++)	
					{
						tmp=ret*V[j][k];
						if(tmp>Lim) break;
						V[i].push_back(tmp);
					}
				}
				
			}
			sort(V[i].begin(),V[i].end());
			sum+=V[i].size();
		}
		
		cout<<sum<<endl;
	}

Compile as
g++ proj_204.cpp -lgmpxx -lgmp

Advertisements

May 24, 2010 - Posted by | Programming

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: