Given a number n. Find its next prime

Constraint : n<=10^9

Time : 1 sec

Is there any good approach

If yes pls share

Given a number n. Find its next prime

Constraint : n<=10^9

Time : 1 sec

Is there any good approach

If yes pls share

```
#Here is the python implementation
n=int(input())
if n%2==0:
st=n+1
else:
st=n+2
for I in range(st, 10**9 +8, 2):
if is_prime(i):
res=I
break
#res is your answer
print (res)
```

Sieve algorithm should work…but constraint are high… So.

The naive iterative approach should work because we have to check at most 10^6 or less to find next prime.