My Weblog

Blog about programming and math

Project Euler 293

Project euler problem 293 does not require intensive algorithm skills.Generate all the admissible number.They are around 6k less then 10^9 and using some probabilistic method check the next prime. Remember problem ask for ” all distinct pseudo-Fortunate numbers ” so be careful before summing all the numbers.c++ code. Happy solving 🙂

#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>
#define lim 5e15
typedef mpz_class _int;
using namespace std;
vector<_int> V[150],F;
vector<_int> P;
 void isprime()
	{

		bool b[1000];
		memset(b,0,sizeof b);
		for(int i=2;i*i<1000;i++) if(!b[i]) for(int j=i*i;j<1000;j+=i) b[j]=1;
		for(int i=2;i<1000;i++) if(!b[i]) P.push_back(_int(i));
	}

int main()
	{
		isprime();
		int n=P.size();
		_int Lim=1;for(int i=1;i<=9;i++) Lim=Lim*10;
		_int ret=1,tmp;
		while(1) { ret=ret*P[0];if(ret>=Lim) break; V[0].push_back(ret);}
		
		sort(V[0].begin(),V[0].end());
		for(int i=1;i<150;i++)
		{
			ret=1;
			while(1)
			{
				ret=ret*P[i];
				if(ret>=Lim) break;
				tmp=1;
				for(int j=0;j<V[i-1].size();j++)
				{
					tmp=ret*V[i-1][j];
					if(tmp>=Lim) break;	
					V[i].push_back(tmp);

				}			
				sort(V[i].begin(),V[i].end());
			}
		}
		for(int i=0;i<150;i++)
		{
			if(V[i].size()==0) continue;
			for(int j=0;j<V[i].size();j++) 
			F.push_back(V[i][j]);
			
		}
		sort(F.begin(),F.end());

		_int sum=0;
		set<_int> s;
		int len=F.size();
		for(int i=0;i<len;i++) 
		{
			/*for(_int m=2;;m++)
			{
				_int t=F[i]+m;
				if(t>=Lim) break;
				if(mpz_probab_prime_p(t.get_mpz_t(),5)) {s.insert(m);break;}
			}*/
			_int next,curr=F[i]+1;
			mpz_nextprime(next.get_mpz_t(),curr.get_mpz_t());
			s.insert(next-curr+1);
		}
		for(set<_int> :: iterator it=s.begin();it!=s.end();it++) sum+=(*it);
		cout<<sum<<endl;
	}
	

compile g++ proj_293.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: