Program to find the next prime number | Python3 implementation of the approach ; Function that returns True if n is prime else returns False ; Corner cases ; This is checked so that we can skip middle five numbers in below loop ; Function to return the smallest prime number greater than N ; Base case ; Loop continuously until isPrime returns True for a number greater than n ; Driver code
import math NEW_LINE def isPrime ( n ) : NEW_LINE INDENT if ( n <= 1 ) : NEW_LINE INDENT return False NEW_LINE DEDENT if ( n <= 3 ) : NEW_LINE INDENT return True NEW_LINE DEDENT if ( n % 2 == 0 or n % 3 == 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT for i in range ( 5 , int ( math . sqrt ( n ) + 1 ) , 6 ) : NEW_LINE INDENT if ( n % i == 0 or n % ( i + 2 ) == 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT return True NEW_LINE DEDENT def nextPrime ( N ) : NEW_LINE INDENT if ( N <= 1 ) : NEW_LINE INDENT return 2 NEW_LINE DEDENT prime = N NEW_LINE found = False NEW_LINE while ( not found ) : NEW_LINE INDENT prime = prime + 1 NEW_LINE if ( isPrime ( prime ) == True ) : NEW_LINE INDENT found = True NEW_LINE DEDENT DEDENT return prime NEW_LINE DEDENT N = 3 NEW_LINE print ( nextPrime ( N ) ) NEW_LINE