Find the largest composite number that divides N but is strictly lesser than N | Python3 program to find the largest composite number that divides N which is less than N ; Function to check whether a number is prime or not ; Corner case ; Check from 2 to n - 1 ; Function that find the largest composite number which divides N and less than N ; Find the prime number ; Driver Code ; Get the smallest prime factor ; Check if ( N / a ) is prime or not . If Yes print " - 1" ; Else print largest composite number ( N / a )
import math NEW_LINE def isPrime ( n ) : NEW_LINE INDENT if ( n <= 1 ) : NEW_LINE INDENT return False ; NEW_LINE DEDENT for i in range ( 2 , n ) : NEW_LINE INDENT if ( n % i == 0 ) : NEW_LINE INDENT return False ; NEW_LINE DEDENT DEDENT return True ; NEW_LINE DEDENT def getSmallestPrimefactor ( n ) : NEW_LINE INDENT for i in range ( 2 , ( int ) ( math . sqrt ( n ) + 1 ) ) : NEW_LINE INDENT if ( n % i == 0 ) : NEW_LINE INDENT return i ; NEW_LINE DEDENT DEDENT return - 1 NEW_LINE DEDENT N = 100 ; NEW_LINE a = getSmallestPrimefactor ( N ) ; NEW_LINE if ( ( isPrime ( ( int ) ( N / a ) ) ) ) : NEW_LINE INDENT print ( - 1 ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( ( int ) ( N / a ) ) ; NEW_LINE DEDENT