Java | Reuse LC 204 | Explained
Prerequisite: LC 204. Count Primes \nIdea:\n Reuse LC 204 to count primes upto n.\n This implementation is long but is efficient. Use any implementation of your
**Prerequisite:** [LC 204. Count Primes](https://leetcode.com/problems/count-primes/discuss/1141636/Java-or-Easy-or-Sieve-of-Eratosthenes) \n**Idea:**\n* Reuse LC 204 to count primes upto n.\n* This implementation is long but is efficient. Use any implementation of your choice to count primes up to n\n* If there are p primes up to n, then they can be placed at any of the p positions, so there are p! ways to permute them\n* The remaining `n - p` composites can be placed at any of the remaining `n - p` positions, so there are `(n - p)!` ways to permute them\n* So total permutations = p! x (n - p)!\n* Example: n = 5\n```\nPrimes = 3, 5 can be placed at positions = 3 or 5\nRemaining = 1, 2, 4 can be placed at positions = 1, 2, 4\nArrangements = 2! x 3! = 2 x 6 = 12 [Ans]\n```\n```\nprivate static final int MOD = (int) (1e9 + 7);\n\npublic int numPrimeArrangements(int n) {\n\tif (n < 3)\n\t\treturn 1;\n\tvar count = countPrimes(n);\n\treturn (int) (factorial(count) * factorial(n - count) % MOD);\n}\n\npublic int countPrimes(int n) {\n\tvar count = 2;\n\tvar sieve = new HashSet<Integer>();\n\taddToSieve(sieve, 3, n);\n\n\tfor (var j = 5; j <= n; j += 2)\n\t\tcount += checkPrime(j, sieve, n);\n\treturn count;\n}\n\nprivate void addToSieve(Set<Integer> sieve, int prime, int n) {\n\tsieve.add(prime);\n\tfor (var i = prime * prime; i <= n; i += prime)\n\t\tsieve.add(i);\n}\n\nprivate int checkPrime(int j, Set<Integer> sieve, int n) {\n\tif (sieve.contains(j))\n\t\treturn 0;\n\tvar i = 5;\n\tvar w = 2;\n\n\twhile (i * i <= j) {\n\t\tif (j % i == 0)\n\t\t\treturn 0;\n\t\ti += w;\n\t\tw = 6 - w;\n\t}\n\n\taddToSieve(sieve, j, n);\n\treturn 1;\n}\n\nprivate long factorial(int a) {\n\tvar fac = 1L;\n\tfor (var i = 2; i <= a; i++)\n\t\tfac = fac * i % MOD;\n\treturn fac;\n}\n```\n***Please upvote if this helps***
['Java']