[Java] Simple sieve in O(n log log n)
\nclass Solution {\n    private static final long MOD = (long) 1e9 + 7;\n    \n    public int numPrimeArrangements(int n) {\n        int primesCount = countNumb
```\nclass Solution {\n    private static final long MOD = (long) 1e9 + 7;\n    \n    public int numPrimeArrangements(int n) {\n        int primesCount = countNumberOfPrimes(n);\n        long result = factorial(primesCount) * factorial(n - primesCount) % MOD;\n        \n        return (int) result;\n    }\n    \n    private int countNumberOfPrimes(int n) {\n        int answer = 0;\n        boolean[] isNotPrime = new boolean[n + 1];\n        \n        for (int i = 2; i <= n; i++) {\n            if (isNotPrime[i])\n                continue;\n            \n            answer++;\n            for (int j = i * i; j <= n; j += i)\n                isNotPrime[j] = true;\n        }\n        \n        return answer;\n    }\n    \n    private long factorial(int n) {\n        long answer = 1;\n        while (n > 1) {\n            answer = (answer * n) % MOD;\n            n--;\n        }\n        \n        return answer;\n    }\n}\n```
[]