My Weblog

Blog about programming and math

Project Euler Problem 266

Worth spending 2 days to figure out solution project euler problem 266 although technically i was aware of algorithm [see Knapsack problem] used to solve the problem.Generate two subsets and sort them and doing binary search leads to solution.There are 42 primes less than 190. Divide them in to two sets and generate all the subsets of these two sets. Sort them in increasing order and do a binary search to find out products of subsets near to square root of product. Here is c++ code and it takes 4 min to pop up the answer.

#include<cstdio>
#include<iostream>
#include<gmpxx.h>
#include<vector>
#include<algorithm>
#include<ctime>
using namespace std;
vector<mpz_class> v,v_l,v_r;
mpz_class ret;
void _prime()
	{
		bool p[190];
		memset(p,0,sizeof p);
		for(int i=2;i*i<190;i++)
			if(!p[i])
				for(int j=i*i;j<190;j+=i) p[j]=1;
		mpz_class cnt=1;
		for(int j=2;j<190;j++) if(!p[j]) cnt*=j,v.push_back(mpz_class(j));
		//cout<<endl;
		//cout<<cnt<<" "<<sqrt(cnt)<<" "<<v.size()<<endl;
		ret=sqrt(cnt);
		//cout<<ret*ret<<" "<<cnt<<endl;
	}	
int main()
	{
		clock_t start,end;
		double rutime;
		start=clock();
		_prime();
		for(int i=0;i<(1<<21);i++)
		{
			mpz_class t_1=1,t_2=1;
			for(int j=0;j<21;j++) if(i&(1<<j))t_1*=v[j],t_2*=v[j+21];
			v_l.push_back(t_1);
			v_r.push_back(t_2);
		}
		
		
		sort(v_l.begin(),v_l.end());
		sort(v_r.begin(),v_r.end());
		//cout<<v_l.size()<<v_r.size()<<endl;
		//for(int i=0;i<10;i++) cout<<v[i]<<endl;
		mpz_class m=0;
		for(int i=0;i<v_l.size();i++)
		{
			mpz_class k=*(upper_bound(v_r.begin(),v_r.end(),ret/v_l[i])-1);
			if(m<(k*v_l[i]))m=k*v_l[i];
		}
		cout<<m<<endl;
		end=clock();
		rutime=((end-start)/(double)CLOCKS_PER_SEC);
		cout<<"runtime is "<<rutime<<endl;
	}

compile with g++ proj_266.cpp -lgmpxx -lgmp

Advertisements

April 25, 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: