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.

#include<cstdio>
#include<iostream>
#include<vector>
using namespace std;

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

void prime()
	{
		b[0]=b[1]=1;
		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="";
		while(n)
		{
			s=char(n%10+'0')+s;
			n/=10;
		}
		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()
	{
		prime();
		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;
						f=1;
						}
					}									
				}	
			}
		}
	}
Advertisements

July 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: