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

No comments yet.

Advertisements

## Leave a Reply