Check if factorial of N is divisible by the sum of squares of first N natural numbers | Python 3 implementation of the approach ; Function to count number of times prime P divide factorial N ; Lengendre Formula ; Function to find count number of times all prime P divide summation ; Formula for summation of square after removing n and constant 6 ; Loop to traverse over all prime P which divide summation ; If Number itself is a Prime Number ; Driver Code
from math import sqrt NEW_LINE def checkfact ( N , countprime , prime ) : NEW_LINE INDENT countfact = 0 NEW_LINE if ( prime == 2 or prime == 3 ) : NEW_LINE INDENT countfact += 1 NEW_LINE DEDENT divide = prime NEW_LINE while ( int ( N / divide ) != 0 ) : NEW_LINE INDENT countfact += int ( N / divide ) NEW_LINE divide = divide * divide NEW_LINE DEDENT if ( countfact >= countprime ) : NEW_LINE INDENT return True NEW_LINE DEDENT else : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT def check ( N ) : NEW_LINE INDENT sumsquares = ( N + 1 ) * ( 2 * N + 1 ) NEW_LINE countprime = 0 NEW_LINE for i in range ( 2 , int ( sqrt ( sumsquares ) ) + 1 , 1 ) : NEW_LINE INDENT flag = 0 NEW_LINE while ( sumsquares % i == 0 ) : NEW_LINE INDENT flag = 1 NEW_LINE countprime += 1 NEW_LINE sumsquares /= i NEW_LINE DEDENT if ( flag ) : NEW_LINE INDENT if ( checkfact ( N - 1 , countprime , i ) == False ) : NEW_LINE INDENT return False NEW_LINE DEDENT countprime = 0 NEW_LINE DEDENT DEDENT if ( sumsquares != 1 ) : NEW_LINE INDENT if ( checkfact ( N - 1 , 1 , sumsquares ) == False ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT return True NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 5 NEW_LINE if ( check ( N ) ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT DEDENT