_1175.java

packagecom.fishercoder.solutions.secondthousand;

importjava.math.BigInteger;
importjava.util.Arrays;

publicclass_1175 {
publicstaticclassSolution1 {
// credit:
// https://leetcode.com/problems/prime-arrangements/discuss/371884/Simple-Java-With-comment-sieve_of_eratosthenes
staticintMOD = 1000000007;

publicstaticintnumPrimeArrangements(intn) {
intnumberOfPrimes = generatePrimes(n);
BigIntegerx = factorial(numberOfPrimes);
BigIntegery = factorial(n - numberOfPrimes);
returnx.multiply(y).mod(BigInteger.valueOf(MOD)).intValue();
 }

publicstaticBigIntegerfactorial(intn) {
BigIntegerfac = BigInteger.ONE;
for (inti = 2; i <= n; i++) {
fac = fac.multiply(BigInteger.valueOf(i));
 }
returnfac.mod(BigInteger.valueOf(MOD));
 }

publicstaticintgeneratePrimes(intn) {
boolean[] prime = newboolean[n + 1];
Arrays.fill(prime, 2, n + 1, true);
for (inti = 2; i * i <= n; i++) {
if (prime[i]) {
for (intj = i * i; j <= n; j += i) {
prime[j] = false;
 }
 }
 }
intcount = 0;
for (inti = 0; i < prime.length; i++) {
if (prime[i]) {
count++;
 }
 }

returncount;
 }
 }
}