LeetCode No.1175
这里用的埃氏筛。因为做题很少刷到筛法相关，会忘，所以还是整理。
class Solution {
public int numPrimeArrangements(int n) {
final int mod = 1000000007;
if (n == 1) {
return 1;
}
// 转为求 1 到 n 有几个质数
// 使用埃式筛法
int count = 0;
boolean[] isNotPrime = new boolean[n + 1];
for (int i = 2; i <= n; i++) {
if (!isNotPrime[i]) {
count++;
for (int j = 1; j*i <= n; j++) {
isNotPrime[j*i] = true;
}
}
}
long result = 1;
for (int i = 2; i <= count; i++) {
result = Math.floorMod(result * i, mod);
}
for (int i = 2; i <= n-count; i++) {
result = Math.floorMod(result * i, mod);
}
return (int)result;
}
}
埃氏筛
因为质数的倍数不为质数，且已知最小的质数为 2。则从 2 开始，对质数进行遍历，将当前质数的 n 倍数都进行标记，不带标记的则为质数，可继续参与遍历。
欧拉筛
埃氏筛存在重复标记的问题，如对质数 2 和 3 的倍数进行标记时，{6, 12, 18, 24 …} 都会被重复标记。
当给定的范围越大，则重复标记的情况越严重。
欧拉筛通过最小质数因子判断来结束逻辑。
1175 使用欧拉筛处理。
class Solution {
public int numPrimeArrangements(int n) {
final int mod = 1000000007;
if (n == 1) {
return 1;
}
// 转为求 1 到 n 有几个质数
// 使用欧拉筛法
int count = 0;
boolean[] isNotPrime = new boolean[n + 1];
int[] primeArray = new int[n];
// 从最小质数 2 开始遍历
for (int i = 2; i <= n; i++) {
// 如果是质数，则加入质数队列
if (!isNotPrime[i]) {
primeArray[count++] = i;
}
// 当前数 i 和 质数队列里的质数依次相乘，产生的合数都不为质数
for (int j = 0; j < n && i*primeArray[j] <= n; j++) {
isNotPrime[i*primeArray[j]] = true;
// 关键步骤，i 在质数队列中找到最小质数因子，停止
if (i % primeArray[j] == 0) {
break;
}
}
}
long result = 1;
for (int i = 2; i <= count; i++) {
result = Math.floorMod(result * i, mod);
}
for (int i = 2; i <= n-count; i++) {
result = Math.floorMod(result * i, mod);
}
return (int)result;
}
}