# OEG-Editorial

Author: vishalx4
Editorialist: kaneki99

CAKEWALK

# PREREQUISITES:

Number Theory, Maths

# PROBLEM:

You are given a Pythagorean Prime you need to print the next two Pythagorean primes

# EXPLANATION:

A prime is called a Pythagorean prime if it can be represented in the form of
4 * n+1 where n is an integer
Eg 5 = 4 * 1 + 1
13 = 4 * 3 + 1

So given a Pythagorean prime we would iterate to the next number till we find next Pythagorean prime Or we can generate all Pythagorean primes till 10^6 and print the next two for each query

Editorialist's Solution
``````
#include
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF (int)1e9
#define EPS 1e-9
#define PI 3.1415926535897932384626433832795
#define all(a) a.begin(), a.end()
#define x first
#define y second
#define MOD 1000000007
typedef vector vi;
typedef vector vvi;
typedef pair ii;
typedef vector vii;
typedef long long ll;
typedef vector vll;
typedef vector vvll;
typedef double ld;
vi pyPrime;
void sieve() {
int maxa = 1e6;
vector c(maxa + 1, true);
for (int i = 4; i <= maxa; i += 2) c[i] = false;
for (ll i = 3; i * i <= maxa; i++) {
if (c[i]) {
for (int j = i * i; j <= maxa; j += i) c[j] = false;
}
}
for (int i = 2; i <= maxa; i++) {
if (c[i]) {
float num = i;
num -= 1;
num /= 4;
if (ceil(num) == floor(num)) pyPrime.pb(i);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
sieve();
int tc;
cin >> tc;
while (tc--) {
int n;
cin >> n;
int index = lower_bound(all(pyPrime), n) - pyPrime.begin();
cout << pyPrime[index + 1] << " " << pyPrime[index + 2] << "\n";
}
return 0;
}
``````