[daily question] 1175 Prime permutation

I feel that I don't practice much in this field .
Make a summary ...

204. Count prime
subject ：
Given integer n , return All integers less than nonnegative n The number of prime numbers .
Definition of prime number ： In more than 1 Of the natural number , except 1 And a natural number that has no more factors than itself .

• enumeration

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;
    }
}

• Ethmoid ：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/

If a number A Prime number , that 2A,3A,…,n*A It must not be a prime number
So it can be [1,n] In this range , From the very beginning 2,3 Start initializing the number after the prime number ！

class Solution {
    
    public int countPrimes(int n) {
    
        int[] isPrime = new int[n];
        // fill isPrime Every element of an array is 1
        Arrays.fill(isPrime, 1);
        int count = 0;
        for (int i = 2; i < n; ++i) {
    
            if (isPrime[i] == 1) {
    
                /** *  explain i Prime number ！ */
                count++;
                if ((long) i * i < n) {
    
                    for (int j = i * i; j < n; j += i) {
    
                        isPrime[j] = 0;
                    }
                }
            }
        }
        return count;
    }
}

There is a better way to sift this question —— Linear sieve , But it doesn't belong to the written examination / Interview scope , There is no need to master .

• Linear sieve

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. Permutation of prime numbers
[ mathematics + Prime number + Factorial ]
Refer to the explanation of the question ：https://leetcode.cn/problems/prime-arrangements/solution/1175-zhi-shu-pai-lie-java-100-by-wa-pian-bo17/

• [1,n] How many primes are there
• ans == Prime number ！* Nonprime number ！

According to the meaning , The problem can be transformed into a solution n The number of prime numbers within , Write it down as a, At the same time, the number of non prime numbers is b = n - a.
The number of placement schemes for prime numbers is a!, The number of placement schemes for non prime numbers is b!, according to 「 Multiplication principle 」 The total number of placement schemes is 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);
	}

	// Factorial 
	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;
	}
}

Reference resources ：https://leetcode.cn/problems/prime-arrangements/solution/by-ac_oier-t3lk/
The meter + Two points + mathematics
Can pass 「 The meter 」 The way to 100 Primes within are preprocessed to arrays list in , For each n for , We find the first satisfaction 「 Value less than or equal to n」 The location of , So we know n The number of prime numbers within the range .

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;
    }
}