My Weblog

Blog about programming and math

Project euler problem 291

Project euler problem 291. First brute force for small primes and realized the primes are form of (n^2+1)/2 where n is odd [Online integer sequence]. This problem was similar to problem 216 in which we have to count the primes of form 2n^2-1. I rather brute force it with gmp library functions which is quite faster than my own rabin miller implementation but still shank-tonelli is required algorithm under one minute rule and i am trying to figure out this algorithm. Here is code which runs less than 20 min for answer on my pc.

#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;
int main()
	{
		_int cnt=0,k;
		cout<<lim<<endl;
		for(_int i=3;;i+=2)
		{
			k=(i*i+1)/2;
			if(k>=lim) break;
			if(mpz_probab_prime_p(k.get_mpz_t(),5)) cnt++;
		}
		cout<<cnt<<endl;

	}
Advertisements

May 10, 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: