Next Prime Number

Given an integer n, you are required to find the smallest prime number strictly greater than n.

A prime number is a natural number greater than 1 that has no divisors other than 1 and itself. In mathematical terms, a number \(p\) is prime if it satisfies \(p > 1\) and for every integer \(a\) such that \(1 < a < p\), \(p \mod a \neq 0\).

Your task is to implement an efficient algorithm to determine the next prime number after n.

inputFormat

The input consists of a single integer \(n\) provided via standard input (stdin).

You can assume \(n\) is in the range of typical integer values.

outputFormat

Output a single integer which is the smallest prime number greater than \(n\) using standard output (stdout).

17

19