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>
#define lim 5e15
typedef mpz_class _int;
using namespace std;
int main()
		_int cnt=0,k;
		for(_int i=3;;i+=2)
			if(k>=lim) break;
			if(mpz_probab_prime_p(k.get_mpz_t(),5)) cnt++;


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