Heraldic Prediction

시간 제한0.5초메모리 제한2048 MB

요약
n이 10^16 이하로 주어질 때, 모든 소수 p에 대해 p^2 + m이 합성수가 되는 짝수 m을 n과 n+50 사이에서 찾아 출력한다.
난이도

어려움10점 중 8점

유형
정수론, 수학, 완전 탐색
정답자
아직 제출이 없습니다

문제

After beating your friend Reyn in various games such as Chess, Backgammon, Checkers, and Battleships, you have almost managed to convince him that you possess the Monado -- a magic sword that lets you see the future. In an act of desparation, he offers you one last challenge. He will tell you a number nn between 1 and 101610^{16} and then secretly pick a prime number pp of any size. It will then be your job to tell him an even number mm, where n<m<n+50n < m < n+50, and p2+mp^2 + m is a composite number (a composite number is a positive integer, which can be formed by multiplying two smaller positive integers). If both of those conditions are fulfilled, it will be clear that the future truly is yours to decide. Luckily, you suspect that Reyn might not have thought this game through very well, and that it is probably possible to determine an mm, which adds up to a composite number with any possible value of pp.

With this knowledge in mind, make a program that can beat Reyn, no matter what numbers he picks.

입력

The input consists of:

  • A line with a single integer nn (1≤n≤10161 \leq n \leq 10^{16}), the number chosen by Reyn.

출력

Output a single even number mm, where n<m<n+50n < m < n+50 and p2+mp^2 + m is composite for any prime pp.

If there are multiple valid solutions, you may output any one of them.

예제2

  1. 예제 1

    입력
    5
    
    예상 출력
    26
    
  2. 예제 2

    입력
    4242
    
    예상 출력
    4256