My Weblog

Blog about programming and math

Project Euler 146

Brute forced with bit of analysis. After carefully observation , the numbers should be multiple of 5. For n = 1 or 4 mod 5, n^2=1 \mod 5 then n^2+9=0  \mod  5. Similarly for n = 2 or 3 mod 5 n^2=4  \mod  5 then n^2+1=0 \mod  5. It takes couple of minutes on my office’s faster computer.
Edit:: Forum suggests ” n must be congruent to 10, 80, 130 or 200 mod 210 [2,3,5,7]” so this could be make bit more faster using this fact.Changed the loop from for(_int i=5;i<150000000;i+=5) to for(_int i=10;i<150000000;i+=10) makes it bit faster.

#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;
int main()
	{
		_int sum=0,k;
		for(_int i=10;i<150000000;i+=10)
		{
			k=( i*i+1 );
			if(mpz_probab_prime_p(k.get_mpz_t(),5) ) 
			 {
				_int next , curr = k;
				mpz_nextprime(next.get_mpz_t(),curr.get_mpz_t()); 
				if( next == ( i*i + 3 ) )
				 {
					curr= next ; 
					mpz_nextprime(next.get_mpz_t() , curr.get_mpz_t());
					if( next == ( i*i + 7 ) ) 
					 {
						curr = next;
						mpz_nextprime(next.get_mpz_t() , curr.get_mpz_t());
						if ( next == ( i*i + 9 ) ) 
						 {
							curr = next;
							mpz_nextprime(next.get_mpz_t() , curr.get_mpz_t());
							if(next == ( i*i + 13 ) ) 
							 {
								curr = next;
								mpz_nextprime(next.get_mpz_t() , curr.get_mpz_t());
								if( next == ( i*i + 27 )) sum += i;
							 }
						 }
					 }
				}
			}
		}	
		cout<<sum<<endl;	

	}
Advertisements

June 22, 2011 - 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: