Java solution beats 100% time & space
Example n = 5\n1   2   3   4   5\n\n1 & 4 is not prime number => number of choice is 2 * 1;\n2 & 3 & 5 is prime number => number of choice is 3 * 2 * 1\n\nBased
Example n = 5\n1   2   3   4   5\n\n1 & 4 is not prime number => number of choice is 2 * 1;\n2 & 3 & 5 is prime number => number of choice is 3 * 2 * 1\n\nBased on this intuition, I count number of prime number from [1, n]. Number of non-prime is n-nbrPrime.\nThe result is factorial(nbrPrime) * factorial(nonPrime)\n\n\n```\nclass Solution {\n\tprivate final int mod = 1000000007;\n\n\tpublic int numPrimeArrangements(int n) {\n\t\tint nbrPrime = 0;\n\t\tfor (int i = 1; i <= n; i++) {\n\t\t\tif (isPrime(i)) nbrPrime++;\n\t\t}\n\t\tint nonPrime = n - nbrPrime;\n\t\tlong res = 1;\n\t\tfor (int i = 2; i <= Math.max(nbrPrime, nonPrime); i++) {\n\t\t\tif (i <= Math.min(nbrPrime, nonPrime)) {\n\t\t\t\tres = (res * i * i) % mod;\n\t\t\t} else {\n\t\t\t\tres = (res * i) % mod;\n\t\t\t}\n\t\t}\n\t\treturn (int) res;\n\t}\n\n\tpublic boolean isPrime(int n) {\n\t\tif (n < 2) return n == 2;\n\t\tfor (int i = 2; i <= n / 2; i++) {\n\t\t\tif (n % i == 0) return false;\n\t\t}\n\t\treturn true;\n\t}\n}\n```
[]