Trial division Algorithm for Prime Factorization | Function to check if a number is a prime number or not ; Initializing with the value 2 from where the number is checked ; Computing the square root of the number N ; While loop till the square root of N ; If any of the numbers between [ 2 , sqrt ( N ) ] is a factor of N Then the number is composite ; If none of the numbers is a factor , then it is a prime number ; Driver code ; To check if a number is a prime or not
def TrialDivision ( N ) : NEW_LINE INDENT i = 2 NEW_LINE k = int ( N ** 0.5 ) NEW_LINE while ( i <= k ) : NEW_LINE INDENT if ( N % i == 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT i += 1 NEW_LINE DEDENT return 1 NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 49 NEW_LINE p = TrialDivision ( N ) NEW_LINE if ( p ) : NEW_LINE INDENT print ( " Prime " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " Composite " ) NEW_LINE DEDENT DEDENT