# My Weblog

## 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;

}
```