OEG-Editorial

editorial
, , ,
1

PROBLEM LINK:One Eyed Ghoul

Author: vishalx4
Editorialist: kaneki99

DIFFICULTY:

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