Ta phải tìm số hoán vị từ 1 đến n để các số nguyên tố được đặt ở chỉ số nguyên tố. Các câu trả lời có thể lớn, trả về modulo câu trả lời 10 ^ 9 + 7. Vì vậy, nếu n =5, thì kết quả sẽ là 12. Vì vậy sẽ có 12 hoán vị. một hoán vị có thể có sẽ là [1,2,5,4,3], một hoán vị không hợp lệ là [5,2,3,4,1] vì 5 được đặt ở chỉ số 1, đó không phải là số nguyên tố.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Xác định một phương thức được gọi là getNum, như sau -
- prime:=danh sách tất cả các số nguyên tố từ 2 đến 100
- đặt i:=0
- while i <độ dài của danh sách nguyên tố
- nếu số nguyên tố [i]> n, thì trả về i
- i:=i + 1
- độ dài trả về của số nguyên tố
- Vấn đề thực tế sẽ được giải quyết như sau
- x:=getNum (n), p:=1, m:=10 ^ 9 + 7
- cho i:=x xuống 0
- p:=p * i
- p:=p mod m
- cho i:=n - x xuống 0
- p:=p * i
- p:=p mod m
- trả về p
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
class Solution(object): def getNum(self,n): primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97] i = 0 while i < len(primes): if primes[i]>n: return i i+=1 return len(primes) def numPrimeArrangements(self, n): """ :type n: int :rtype: int """ x = self.getNum(n) p = 1 m = 1000000000+7 for i in range(x,0,-1): p*=i p%=m for i in range(n-x,0,-1): p*=i p%=m return p ob1 = Solution() print(ob1.numPrimeArrangements(100))
Đầu vào
100
Đầu ra
682289015