Python O( n*sqrt(n) ) sol. by prime judgement. 90%+ [ With explanation ]
Python O( n * sqrt(n) ) sol. by prime judgement.\n\n---\n\nHint:\nBuild a helper function to judge whether a number k is a prime or not.\n\n---\n\nNote:\nRememb
Python O( n * sqrt(n) ) sol. by prime judgement.\n\n---\n\nHint:\nBuild a helper function to judge whether a number k is a prime or not.\n\n---\n\nNote:\nRemember to take **modulo** (**10^9 + 7**), which is [defined by description](https://leetcode.com/problems/prime-arrangements/).\n\n---\n\n```\nfrom math import factorial\nfrom math import sqrt\nclass Solution:\n    \n    def judge_prime( self, k:int) -> bool:\n        \'\'\'\n        Input: positive integer\n        Output: True for prime number. Otherwise, retunr False\n        \'\'\'\n        \n        if k == 1:\n            return False\n        \n        if k == 2:\n            return True\n        \n        for i in range(2, int( sqrt(k)+1 ) ):\n            \n            if k % i == 0:\n                return False\n            \n        return True\n    \n    \n    \n    def numPrimeArrangements(self, n: int) -> int:\n        \'\'\'\n        Input: n\n        Output: Prime arrangements for n\n        \'\'\'\n        \n        \n        # modulo constant defined by description\n        mod_constant = int(1e9)+7\n        \n        counter_of_prime = 0\n        \n        # check positive integer from 1 to n\n        for i in range(1,n+1):\n            \n            if self.judge_prime(i):\n                counter_of_prime += 1\n        \n        # Let q as counter_of_prime\n        # then all permutation\n        # = ( q! * ( n-q)! ) mod (10^9 + 7)\n        all_permutation = ( factorial(counter_of_prime) * factorial(n-counter_of_prime) ) % mod_constant\n        \n        return all_permutation\n```\n\n---\n\nReference:\n\n[1] [Wiki: Prime Number](https://en.wikipedia.org/wiki/Prime_number)\n\n[2] [Python official docs about math.sqrt()](https://docs.python.org/3/library/math.html#math.sqrt)\n\n[3] [Python official docs about math.factorial()](https://docs.python.org/3/library/math.html#math.factorial)
['Math', 'Iterator', 'Python']