My Weblog

Blog about programming and math

Project Euler Problem 60

This problem took some time to figure out the upper bound on prime. First i took 10^6 as upper bound but answer was not available under one minute rule. I changed it 10^5 and later 10^4. Easy problem but proving bound is hard and i don’t know how to prove other then trial and error.

using namespace std;

bool b[10000];
vector<int> v;

void prime()
		for(int i=2;i*i<10000;i++) if (!b[i]) for (int j=i*i;j<10000;j+=i) b[j]=1;
		for(int i=0;i<10000;i++) if(!b[i])v.push_back(i);
		//for(int i=0;i<10;i++) cout<<v[i]<<"  ";cout<<endl;
int _int(string s)
		int tmp=0;
		for(int i=0;i<s.size();i++) tmp =tmp*10+(s[i]-'0');
		return tmp;
string str(int n)
		string s="";
		return s;
bool bp(int n)
		if(n<2) return 1;
		if(n==2) return 0;
		if(n%2==0) return 1;
		for(int i=3;i*i<=n;i+=2) if(n%i==0) return 1;
		return 0;
int main()
		int n=v.size(),f=0;
		for(int i=0;i+4<n && !f;i++)
			for(int j=i+1;j+3<n && !f;j++)
				if(bp(_int(str(v[i])+str(v[j]))) || bp(_int(str(v[j])+str(v[i])))) continue;
				for(int k=j+1;k+2<n && !f ;k++)
					if(bp(_int(str(v[i])+str(v[k]))) || bp(_int(str(v[k])+str(v[i]))))continue;//i,k
					if(bp(_int(str(v[j])+str(v[k]))) || bp(_int(str(v[k])+str(v[j]))))continue;//j,k
					for(int l=k+1;l+1<n && !f ;l++) 
						if(bp(_int(str(v[i])+str(v[l]))) || bp(_int(str(v[l])+str(v[i]))))continue;
						if(bp(_int(str(v[j])+str(v[l]))) || bp(_int(str(v[l])+str(v[j]))))continue;
						if(bp(_int(str(v[k])+str(v[l]))) || bp(_int(str(v[l])+str(v[k]))))continue;
						for(int m=l+1;m<n && !f;m++)
						if(bp(_int(str(v[i])+str(v[m]))) || bp(_int(str(v[m])+str(v[i]))))continue;
						if(bp(_int(str(v[j])+str(v[m]))) || bp(_int(str(v[m])+str(v[j]))))continue;
						if(bp(_int(str(v[k])+str(v[m]))) || bp(_int(str(v[m])+str(v[k]))))continue;								             if(bp(_int(str(v[l])+str(v[m]))) || bp(_int(str(v[m])+str(v[l]))))continue;
						int sum=v[i]+v[j]+v[k]+v[l]+v[m];
						cout<<v[i]<<" "<<v[j]<<" "<<v[k]<<" "<<v[l]<<" "<<v[m]<<" "<<sum<<endl;

July 24, 2010 - Posted by | Programming

No comments yet.

Leave a Reply

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

You are commenting using your 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: