[Java/Python 3] two codes each, count only primes then compute factorials for both w/ analysis.
compute (# of primes)! * (# of composites)!\n\nMethod 1: judge each number by dividing all possible factors\n\nJava\n\n    public int numPrimeArrangements(int n
compute (# of primes)! * (# of composites)!\n\n**Method 1: judge each number by dividing all possible factors**\n\n**Java**\n```\n    public int numPrimeArrangements(int n) {\n        int cnt = 1; // # of primes, first prime is 2.\n        outer:\n        for (int i = 3; i <= n; i += 2) { // only odd number could be a prime, if i > 2.\n            for (int factor = 3; factor * factor <= i; factor += 2)\n                if (i % factor == 0)\n                    continue outer;\n            ++cnt;\n        }\n        long ans = 1;\n        for (int i = 1; i <= cnt; ++i) // (# of primes)!\n            ans = ans * i % 1_000_000_007;\n        for (int i = 1; i <= n - cnt; ++i) // (# of non-primes)!\n            ans = ans * i % 1_000_000_007;\n        return (int)ans;\n    }\n```\n\n----\n\n**Python 3**\n\n```\n    def numPrimeArrangements(self, n: int) -> int:\n        cnt = 1                                                     # number of primes, first prime is 2.\n        for i in range(3, n + 1, 2):                                # only odd number could be a prime, if i > 2.\n            factor = 3\n            while factor * factor <= i:\n                if i % factor == 0:\n                    break \n                factor += 2    \n            else:\n                cnt += 1        \n        ans = 1\n        for i in range(1, cnt + 1):                                # (number of primes)!\n            ans *= i        \n        for i in range(1, n - cnt + 1):                            # (number of non-primes)!\n            ans *= i\n        return ans % (10**9 + 7)\n```\nWith Python lib, we can replace the last 6 lines of the above code by the follows:\n```\n        return math.factorial(cnt) * math.factorial(n - cnt) % (10**9 + 7)\n```\n\n----\n\n**Analysis:**\n\nFor each outer iteration, inner loop cost O(n ^ 0.5).\n\nTime: O(n ^ (3/2)), space: O(1).\n\n----\n\n**Method 2: Sieve - mark all composites based on known primes**\n\n1. Initially, the only know prime is 2; \n2. Mark the prime, prime + 1, prime + 2, ..., times of current known primes as composites.\n\nObviouly, **each time the algorithm runs the inner for loop, it always uses a new prime factor `prime` and also `times` starts with `prime`**, which guarantees there is no repeated composites marking and hence very time efficient.\n\n**Java:**\n\n```\n    public int numPrimeArrangements(int n) {\n        boolean[] composites = new boolean[n + 1];\n        for (int prime = 2; prime * prime <= n; ++prime)\n            for (int cmpst = prime * prime; !composites[prime] && cmpst <= n; cmpst += prime)\n                composites[cmpst] = true;\n        long cnt = IntStream.rangeClosed(2, n).filter(i -> !composites[i]).count();\n        return (int)LongStream.concat(LongStream.rangeClosed(1, cnt), LongStream.rangeClosed(1, n - cnt))\n                              .reduce(1, (a, b) -> a * b % 1_000_000_007);\n    }\n```\n\n----\n\n**Python 3:**\n\n```\n    def numPrimeArrangements(self, n: int) -> int:\n        primes = [True] * (n + 1)\n        for prime in range(2, int(math.sqrt(n)) + 1):\n            if primes[prime]:\n                for composite in range(prime * prime, n + 1, prime):\n                    primes[composite] = False\n        cnt = sum(primes[2:])\n        return math.factorial(cnt) * math.factorial(n - cnt) % (10**9 + 7)\n```\n\n**Analysis:**\n\nTime: O(n * log(logn)), space: O(n).\nFor time complexity analysis in details, please refer to [here](https://en.m.wikipedia.org/wiki/Sieve_of_Eratosthenes).\n\n----\n\n**Brief Summary:**\nMethod 1 and 2 are space and time efficient respectively.
[]