【每日一题】1175. 质数排列

感觉这方面的自己练的有点少。
做一个总结。。。

204. 计数质数
题目：
给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。
质数的定义：在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数。

• 枚举

class Solution {
    
    public int countPrimes(int n) {
    
        int ans = 0;
        for (int i = 2; i < n; ++i) {
    
            ans += isPrime(i) ? 1 : 0;
        }
        return ans;
    }

    public boolean isPrime(int x) {
    
        for (int i = 2; i * i <= x; ++i) {
    
            if (x % i == 0) {
    
                return false;
            }
        }
        return true;
    }
}

• 埃氏筛：https://leetcode.cn/problems/count-primes/solution/nick-by-nickbean-6ej3/、https://leetcode.cn/problems/count-primes/solution/kuai-lai-miao-dong-shai-zhi-shu-by-sweetiee/

如果一个数A是质数，那么2A,3A,…,n*A一定不是质数
所以可以在[1,n]这个范围内，从最开始的2，3就开始给质数后面的数进行做初始化操作！

class Solution {
    
    public int countPrimes(int n) {
    
        int[] isPrime = new int[n];
        //填充isPrime数组的每个元素都是1
        Arrays.fill(isPrime, 1);
        int count = 0;
        for (int i = 2; i < n; ++i) {
    
            if (isPrime[i] == 1) {
    
                /** * 说明i是质数！ */
                count++;
                if ((long) i * i < n) {
    
                    for (int j = i * i; j < n; j += i) {
    
                        isPrime[j] = 0;
                    }
                }
            }
        }
        return count;
    }
}

这题还有更好的筛法——线性筛，但不属于笔试/面试范畴，不需要掌握。

• 线性筛

class Solution {
    
    public int countPrimes(int n) {
    
        List<Integer> primes = new ArrayList<Integer>();
        int[] isPrime = new int[n];
        Arrays.fill(isPrime, 1);
        for (int i = 2; i < n; ++i) {
    
            if (isPrime[i] == 1) {
    
                primes.add(i);
            }
            for (int j = 0; j < primes.size() && i * primes.get(j) < n; ++j) {
    
                isPrime[i * primes.get(j)] = 0;
                if (i % primes.get(j) == 0) {
    
                    break;
                }
            }
        }
        return primes.size();
    }
}

1175. 质数排列
[数学 + 质数 + 阶乘]
参考题解：https://leetcode.cn/problems/prime-arrangements/solution/1175-zhi-shu-pai-lie-java-100-by-wa-pian-bo17/

• [1,n]一共有多少个质数
• ans == 质数！* 非质数！

根据题意，可将问题转换为求 n 以内的质数个数，记为 a，同时可得非质数个数为 b = n - a。
质数的放置方案数为 a!，而非质数的放置方案数为 b!，根据「乘法原理」总的放置方案数为 a!×b!。

class Solution {
    
	int mod = (int) 1e9 + 7;

	public int numPrimeArrangements(int n) {
    
		int prime = 0;
		for (int i = 1; i <= n; i++) {
    
			if (isPrime(i)) {
    
				prime++;
			}
		}
		long ans = factorial(prime);
		ans *= factorial(n - prime);
		return (int) (ans % mod);
	}

	//阶乘
	private long factorial(int num) {
    
		long ans = 1;
		for (int i = 1; i <= num; i++) {
    
			ans *= (long) i;
			ans %= mod;
		}
		return ans;
	}

	private boolean isPrime(int num) {
    
		if (num == 2) {
    
			return true;
		}
		if (num == 1 || num % 2 == 0) {
    
			return false;
		}
		for (int i = 3; i * i <= num; i += 2) {
    
			if (num % i == 0 || i * i == num) {
    
				return false;
			}
		}
		return true;
	}
}

参考：https://leetcode.cn/problems/prime-arrangements/solution/by-ac_oier-t3lk/
打表 + 二分 + 数学
可以通过「打表」的方式将 100 以内的质数预处理到数组 list 中，对于每个 n 而言，我们找到第一个满足「值小于等于 n」的位置，从而得知 n 范围以内的质数个数。

class Solution {
    
    static int MOD = (int)1e9+7;
    static List<Integer> list = new ArrayList<>();
    static {
    
        for (int i = 2; i <= 100; i++) {
    
            boolean ok = true;
            for (int j = 2; j * j <= i; j++) {
    
                if (i % j == 0) ok = false;
            }
            if (ok) list.add(i);
        }
    }
    public int numPrimeArrangements(int n) {
    
        int l = 0, r = list.size() - 1;
        while (l < r) {
    
            int mid = l + r + 1 >> 1;
            if (list.get(mid) <= n) l = mid;
            else r = mid - 1;
        }
        int a = r + 1, b = n - a;
        long ans = 1;
        for (int i = b; i > 1; i--) ans = ans * i % MOD ;
        for (int i = a; i > 1; i--) ans = ans * i % MOD ;
        return (int)ans;
    }
}