完整的网络营销推广方案包括,优化营商环境心得体会个人,网站建设经理岗位职责,企业网站推广营销文章目录1. 题目2. 解题1. 题目
请你帮忙给从 1 到 n 的数设计排列方案#xff0c;使得所有的「质数」都应该被放在「质数索引」#xff08;索引从 1 开始#xff09;上#xff1b;你需要返回可能的方案总数。
让我们一起来回顾一下「质数」#xff1a;质数一定是大于 1…
文章目录1. 题目2. 解题1. 题目
请你帮忙给从 1 到 n 的数设计排列方案使得所有的「质数」都应该被放在「质数索引」索引从 1 开始上你需要返回可能的方案总数。
让我们一起来回顾一下「质数」质数一定是大于 1 的并且不能用两个小于它的正整数的乘积来表示。
由于答案可能会很大所以请你返回答案 模 mod 10^9 7 之后的结果即可。
示例 1输入n 5
输出12
解释举个例子[1,2,5,4,3] 是一个有效的排列
但 [5,2,3,4,1] 不是因为在第二种情况里质数 5 被错误地放在索引为 1 的位置上。示例 2输入n 100
输出682289015提示1 n 100来源力扣LeetCode 链接https://leetcode-cn.com/problems/prime-arrangements 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
判断质数1不是2是质数从3开始不能被2到该数平方根区间所有整数整除的就是质数计数质数有a个则非质数有n-a个排列组合数为 a∗(n−a)a*(n-a)a∗(n−a) 另可参考求大于n的最小质数
class Solution {
public:int numPrimeArrangements(int n) {if(n 1)return 1;int count 0, i, j;unsigned long long ans 1;bool flag;for(i 2; i n; i){flag true;for(j 2; j sqrt(i); j){if(i%j 0){flag false;break;}}if(flag)count;}n n-count;while(n){ans * n--;ans % (long long)(1e9 7);}while(count){ans * count--;ans % (long long)(1e9 7);}return ans;}
};
