Find the minimum number to be added to N to make it a prime number | Function to check if a given number is a prime or not ; Base cases ; This is checked so that we can skip middle five numbers in below loop ; For all the remaining numbers , check if any number is a factor if the number or not ; If none of the above numbers are the factors for the number , then the given number is prime ; Function to return the smallest number to be added to make a number prime ; Base case ; Loop continuously until isPrime returns true for a number greater than n ; If the number is not a prime , then increment the number by 1 and the counter which stores the number to be added ; Driver code
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 i = 5 NEW_LINE while ( i * i <= n ) : NEW_LINE INDENT if ( n % i == 0 or n % ( i + 2 ) == 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT i += 6 NEW_LINE DEDENT return True NEW_LINE DEDENT def findSmallest ( N ) : NEW_LINE INDENT if ( N == 0 ) : NEW_LINE INDENT return 2 NEW_LINE DEDENT if ( N == 1 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT prime , counter = N , 0 NEW_LINE found = False NEW_LINE while ( not found ) : NEW_LINE INDENT if ( isPrime ( prime ) ) : NEW_LINE INDENT found = True NEW_LINE DEDENT else : NEW_LINE INDENT prime += 1 NEW_LINE counter += 1 NEW_LINE DEDENT DEDENT return counter NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 10 NEW_LINE print ( findSmallest ( N ) ) NEW_LINE DEDENT