奇数筛（位运算） + 阶乘 + 排列，求解《204. 计数质数》和《1175. 质数排列》
例题
204. 计数质数
给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。
示例 1：
输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7
答案
奇数筛 · 位运算
var countPrimes = function(n) {
if (n <= 2) return 0
const isCom = new Uint8Array(n)
let ans = 1
for (let i = 3; i < n; i += 2) {
if (isCom[i] === 1) continue
for (let j = i + (i << 1); j < n; j += i << 1) {
isCom[j] = 1
}
ans++
}
return ans
};function countPrimes(n: number): number {
if (n <= 2) return 0 // 小于 2，只有 0， 1 不是质数
const isCom = new Uint8Array(n) // 是否是合数
let ans = 1
for (let i = 3; i < n; i += 2) {
if (isCom[i] === 1) continue;
for (let j = i + (i << 1); j < n; j += i << 1) {
isCom[j] = 1
}
ans++
}
return ans
};class Solution {
function countPrimes($n) {
if ($n <= 2) return 0;
$isCom = array_fill(0, $n, 0);
$ans = 1;
for ($i = 3; $i < $n; $i += 2) {
if ($isCom[$i] === 1) continue;
for ($j = $i + ($i << 1); $j < $n; $j += $i << 1) {
$isCom[$j] = 1;
}
$ans++;
}
return $ans;
}
}func countPrimes(n int) int {
if n <= 2 {
return 0
}
isCom, ans := make([]int, n), 1
for i := 3; i < n; i += 2 {
if isCom[i] == 0 {
for j := i + i << 1; j < n; j += i << 1 {
isCom[j] = 1
}
ans++
}
}
return ans
}class Solution:
def countPrimes(self, n: int) -> int:
if n <= 2: return 0
ans, isCom = 1, [False] * n
for i in range(3, n, 2):
if isCom[i] == False:
for j in range(i + (i << 1), n, i << 1):
isCom[j] = True
ans += 1
return ansclass Solution {
public int countPrimes(int n) {
if (n <= 2) return 0;
int ans = 1;
boolean[] isCom = new boolean[n];
for (int i = 3; i < n; i += 2) {
if (isCom[i] == true) continue;
for (int j = i + (i << 1); j < n; j += i << 1) {
isCom[j] = true;
}
ans++;
}
return ans;
}
}int countPrimes(int n){
if (n <= 2) return 0;
int *isCom = (int *)malloc(sizeof(int) * n);
int ans = 1;
for (int i = 3; i < n; i += 2) {
if (isCom[i] == 1) continue;
for (int j = i + (i << 1); j < n; j += i << 1) {
isCom[j] = 1;
}
ans++;
}
return ans;
}class Solution {
public:
int countPrimes(int n) {
if (n <= 2) return 0;
int ans = 1;
vector<int> isCom(n, 0);
for (int i = 3; i < n; i += 2) {
if (isCom[i] == 1) continue;
for (int j = i + (i << 1); j < n; j += i << 1) {
isCom[j] = 1;
}
ans++;
}
return ans;
}
};public class Solution {
public int CountPrimes(int n) {
if (n <= 2) return 0;
bool[] isCom = new bool[n];
int ans = 1;
for (int i = 3; i < n; i += 2) {
if (isCom[i] == true) continue;
for (int j = i + (i << 1); j < n; j += i << 1) {
isCom[j] = true;
}
ans++;
}
return ans;
}
}1175. 质数排列
请你帮忙给从 1 到 n 的数设计排列方案，使得所有的「质数」都应该被放在「质数索引」（索引从 1 开始）上；你需要返回可能的方案总数。
让我们一起来回顾一下「质数」：质数一定是大于 1 的，并且不能用两个小于它的正整数的乘积来表示。
由于答案可能会很大，所以请你返回答案 模 mod 10^9 + 7 之后的结果即可。
示例 1：
输入：n = 5
输出：12
解释：举个例子，[1,2,5,4,3] 是一个有效的排列，但 [5,2,3,4,1] 不是，因为在第二种情况里质数 5 被错误地放在索引为 1 的位置上。
答案
奇数筛 · 位运算 · 阶乘 · 排列
var numPrimeArrangements = function(n) {
const MOD = 1e9 + 7
let num = countPrimes(n), r = 1, m = n - num
while (num) {
r *= num--
r %= MOD
}
while (m) {
r *= m--
r %= MOD
}
return r
};
const countPrimes = n => {
if (n <= 1) return 0
const isCom = new Uint8Array(n + 1)
let ans = 1
for (let i = 3; i <= n; i += 2) {
if (isCom[i] == 1) continue
for (let j = i + (i << 1); j <= n; j += i << 1) {
isCom[j] = 1
}
ans++
}
return ans
}function numPrimeArrangements(n: number): number {
const MOD = 1e9 + 7
let num = countPrimes(n), m = n - num, r = 1
while (num) {
r *= num--
r %= MOD
}
while (m) {
r *= m--
r %= MOD
}
return r
};
function countPrimes(n: number): number {
if (n <= 1) return 0
const isCom = new Uint8Array(n + 1)
let r = 1
for (let i = 3; i <= n; i += 2) {
if (isCom[i] === 1) continue
for (let j = i + (i << 1); j <= n; j += i << 1) {
isCom[j] = 1
}
r++
}
return r
} class Solution {
const MOD = 1e9 + 7;
function numPrimeArrangements($n) {
$num = $this->countPrimes($n);
return $this->factorial($num) * $this->factorial($n - $num) % self::MOD;
}
function factorial($n) {
$r = 1;
for ($i = 2; $i <= $n; $i++) {
$r = $r * $i % self::MOD;
}
return $r;
}
function countPrimes($n) {
if ($n <= 1) return 0;
$r = 1;
$isCom = array_fill(0, $n + 1, 0);
for ($i = 3; $i <= $n; $i += 2) {
if ($isCom[$i] === 1) continue;
for ($j = $i + ($i << 1); $j <= $n; $j += $i << 1) {
$isCom[$j] = 1;
}
$r += 1;
}
return $r;
}
}const MOD = 1e9 + 7
func numPrimeArrangements(n int) int {
num := countPrimes(n)
return factorial(num) * factorial(n - num) % MOD
}
func factorial(n int) int {
r := 1
for i := 2; i <= n; i++ {
r = r * i % MOD
}
return r
}
func countPrimes(n int) int {
if n <= 1 {
return 0
}
r, isCom := 1, make([]int, n + 1)
for i := 3; i <= n; i += 2 {
if isCom[i] == 0 {
for j := i + i << 1; j <= n; j += i << 1 {
isCom[j] = 1
}
r++
}
}
return r
}class Solution:
MOD = int(1e9 + 7)
def numPrimeArrangements(self, n: int) -> int:
num = self.countPrimes(n)
return self.factorial(num) * self.factorial(n - num) % self.MOD
def factorial(self, n: int) -> int:
r = 1
for i in range(2, n + 1): r = r * i % self.MOD
return int(r)
def countPrimes(self, n: int) -> int:
if n <= 1: return 0
r, isCom = 1, [False] * (n + 1)
for i in range(3, n + 1, 2):
if isCom[i] == True: continue
for j in range(i + (i << 1), n + 1, i << 1):
isCom[j] = True
r += 1
return rclass Solution {
final int MOD = (int)(1e9 + 7);
public int numPrimeArrangements(int n) {
int num = countPrimes(n);
return (int)(factorial(num) * factorial(n - num) % MOD);
}
public long factorial(int n) {
long r = 1;
for (int i = 1; i <= n; i++) r = r * i % MOD;
return r;
}
public int countPrimes(int n) {
if (n <= 1) return 0;
int r = 1;
boolean[] isCom = new boolean[n + 1];
for (int i = 3; i <= n; i += 2) {
if (isCom[i] == true) continue;
for (int j = i + (i << 1); j <= n; j += i << 1) {
isCom[j] = true;
}
r++;
}
return r;
}
}MOD (1e9 + 7)
long factorial(int n) {
long r = 1;
for (int i = 2; i <= n; i++) {
r = r * i % (int)MOD;
}
return r;
}
int countPrimes(int n) {
if (n <= 1) return 0;
int r = 1;
int* isCom = (int*)malloc(sizeof(int) * (n + 1));
for (int i = 3; i <= n; i += 2) {
if (isCom[i] == 1) continue;
for (int j = i + (i << 1); j <= n; j += i << 1) {
isCom[j] = 1;
}
r++;
}
return r;
}
int numPrimeArrangements(int n){
int num = countPrimes(n);
return (int)(factorial(num) * factorial(n - num) % (int)MOD);
}MOD (1e9 + 7)
class Solution {
public:
int numPrimeArrangements(int n) {
int num = countPrimes(n);
return factorial(num) * factorial(n - num) % (int)MOD;
}
long factorial(int n) {
long r = 1;
for (int i = 2; i <= n; i++) r = r * i % (int)MOD;
return r;
}
int countPrimes(int n) {
if (n <= 1) return 0;
int r = 1;
vector<bool> isCom(n + 1, false);
for (int i = 3; i <= n; i += 2) {
if (isCom[i] == true) continue;
for (int j = i + (i << 1); j <= n; j += i << 1) {
isCom[j] = true;
}
r++;
}
return r;
}
};public class Solution {
private int MOD = (int)1e9 + 7;
public int NumPrimeArrangements(int n) {
int num = countPrimes(n);
return (int) (Factorial(num) * Factorial(n - num) % MOD);
}
private long Factorial(int n) {
long r = 1;
for (int i = 2; i <= n; i++) {
r = r * i % MOD;
}
return r;
}
private int countPrimes(int n) {
if (n <= 1) return 0;
int ans = 1;
int[] isCom = new int[n + 1];
for (int i = 3; i <= n; i += 2) {
if (isCom[i] == 1) continue;
for (int j = i + (i << 1); j <= n; j += i << 1) {
isCom[j] = 1;
}
ans++;
}
return ans;
}
}