C➕➕ Easy Solution || 100% Faster || Permutation || Mathematics
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n1. Find total prime numbers from 1 to n\n2. Answer = (permutation of prim
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n1. Find total prime numbers from 1 to n\n2. Answer = (permutation of prime)*(permutation of non-prime)\n\n# Code\n```\nclass Solution {\npublic:\n    \n    int numPrimeArrangements(int n) {\n        vector<int> prime(n+1,1);\n        if(n==1)return 1;\n        prime[0]=0;\n        prime[1]=0;\n\n        int cnt = 0;\n        for(int i = 0 ; i<=n ; i++){\n            if(prime[i]==0)continue;\n            cnt++;\n            for(int j=i*2;j<=n;j+=i)prime[j]=0;\n        }\n\n        const int m = 1e9+7;\n\n        int ans=1;\n        int temp =n-cnt;\n            while(cnt>0){\n                ans = ( 1LL*(ans%m) * 1LL*(cnt%m))%m;\n                cnt--;\n            }\n\n        int fact2 = 1;\n        while(temp>0){\n                fact2 = ( 1LL*(fact2%m) * 1LL*(temp%m))%m;\n                temp--;\n        }\n        \n        return (1LL*(ans%m) * 1LL*(fact2%m))%m;\n    }\n};\n```
['C++']