[C++] Beats 100% Time 100% Space No Sieve Of Eratosthenes
\nclass Solution {\npublic:\n    int numPrimeArrangements(int n) {\n        const long MOD = 1e9 + 7;\n        int count = 0;\n        vector<long> f(n + 1, 1);
```\nclass Solution {\npublic:\n    int numPrimeArrangements(int n) {\n        const long MOD = 1e9 + 7;\n        int count = 0;\n        vector<long> f(n + 1, 1);\n        for(int i = 2; i <= n; i++) {\n            f[i] = f[i - 1] * i;\n            f[i] %= MOD;\n        }\n        for(int p = 2; p <= n; p++) {\n            bool isprime = true;\n            for(int i = 2; i * i <= p; i++) {\n                if(p % i == 0) {\n                    isprime = false;\n                    break;\n                }\n            }\n            if(isprime)\n                count++;\n        }\n        cout << count << endl;\n        return (int)(f[count] % MOD * f[n - count] % MOD);\n    }\n};\n```
[]