$\bullet$ Mình làm bài tập trên codelearn.io
Bài 1: Viết một hàm xác định xem một số nguyên dương đã cho có phải là số nguyên tố hay không.
Định nghĩa: Số nguyên tố là số tự nhiên lớn hơn 1 không phải là tích của hai số tự nhiên nhỏ hơn.
Phân tích: Giả sử số tự nhiên $n>1$ không phải là số nguyên tố và $n=x.y$ với $x,y$ là hai số tự nhiên lớn hơn 1 và bé hơn n, không mất tính tổng quát ta giả sử $x \leq y$ suy ra $x^2 \leq n$ tức là $x \leq \sqrt{n}$
Từ phân tích trên ta rút ra được nếu $n$ không chia hết cho các số nguyên từ 2 đến $\left \lfloor \sqrt{n} \right \rfloor$ thì $n$ là số nguyên tố.
import sys
def prime_number(n):
if n<2:
return 'không phải là số nguyên tố'
i=2
while i*i<=n:
if n%i==0:
return 'không phải là số nguyên tố'
i+=1
return 'là số nguyên tố'
while True:
try:
n=int(input('nhập số tự nhiên: '))
break
except:
print(sys.exc_info()[0])
print('{}'.format(n),prime_number(n))$T(n)=\begin{cases} 2 & \text{ nếu } n<2 \\ 2i & \text{ nếu } n\text{ mod }i=0\\ 2\left\lfloor\sqrt{n}\right\rfloor & \text{ nếu } n\text{ mod }i\neq 0 \end{cases},i=2,3,...,\left \lfloor \sqrt{n} \right \rfloor$
$T(n) \leq 2\sqrt{n} \text{ khi } n\text{ mod }i\neq 0 , \forall i=2,3,...,\left \lfloor \sqrt{n} \right \rfloor$
Suy ra $\frac{T(n)}{\sqrt{n}}$ bị chặn ta viết $T(n)=O(\sqrt{n})$
Chúng ta có thể cải thiện phương pháp này nhanh gấp 2 lần bằng phân tích số học sau, mọi số tự nhiên có thể biểu diễn thành $2k+i,i=0,1,k \in \mathbb{N}$,như vậy để kiểm tra $n$ có phải là số nguyên tố không ta chỉ cần kiểm tra $n$ có chia hết cho 2 hay không sau đó kiểm tra $n$ có chia hết cho tất cả các số có dạng $2k+1 \leq \left \lfloor \sqrt{N} \right \rfloor,k \in \mathbb{Z}^+$.
def is_prime(n):
if n<=2:
return n>1
if n%2==0:
return False
i=3
while i**2<=n:
if n%i==0:
return False
i+=2
return TrueTa tiếp tục cải tiến phương pháp trên với phân tích như sau, mọi số tự nhiên có thể phân tích thành $6k+i,i=-1,0,1,2,3,4,$ mà $6k,6k+2,6k+4$ chia hết cho 2 và $6k+3$ chia hết cho 3 nên các số còn lại có dạng $6k \pm 1.$
Vậy để kiểm tra $n$ có là số nguyên tố hay không ta chỉ cần kiểm tra $n$ có chia hết cho 2 và 3 hay không sau đó kiểm tra $n$ có chia hết cho tất cả các số có dạng $3 < 6k\pm 1\leq \left \lfloor \sqrt{N} \right \rfloor.$
Phương pháp này nhanh hơn gấp 3 lần phương pháp đầu. Mình ước lượng nó bằng cách thực hiện phép tính $\frac{\left \lfloor \sqrt{N} \right \rfloor-5}{3}+1$
import sys
def prime_number(n):
if n<=3:
return n>1
if n%2==0 or n%3==0:
return False
i=5
while i*i<=n:
if n%i==0 or n%(i+2)==0:
return False
i+=6
return True
while True:
try:
n=int(input('nhập vào số tự nhiên n: '))
break
except:
print(sys.exc_info()[0])
print(prime_number(n))Bài 2: In ra $n$ số nguyên tố đầu tiên.
Bằng cách tổng quát hóa các phân tích số học ở bài trên ta được phương pháp gọi là sàng Eratosthenes.(wikipedia.org)
def SieveOfEratosthenes(n):
p=[True]*(n+1)
i=2
while i*i<=n:
if p[i]==True:
for j in range(i*i,n+1,i):
p[j]=False
i+=1
p[0],p[1]=False,False
prime=list()
for i in range(n+1):
if p[i]==True:
prime.append(i)
return prime
Độ phức tạp của thuật toán.
- Khi $i=2$ vòng lặp trong lặp chạy $\frac{n}{2}$ lần.
- Khi $i=3$ vòng lặp trong lặp chạy $\frac{n}{3}$ lần.
- Khi $i=5$ vòng lặp trong lặp chạy $\frac{n}{5}$ lần.
- Khi $i=p \leq \left \lfloor \sqrt{n} \right \rfloor$ vòng lặp trong vòng lặp chạy $\frac{n}{p}$ lần.
Bài 3: Phân tích n ra thừa số nguyên tố.
Thuật toán đơn giản nhất mình nghĩ ra là duyệt qua dãy số nguyên tố đã tạo ra ở trên.
def SieveOfEratosthenes(n):
p,i=[True]*(n+1),2
while i*i<=n:
if p[i]==True:
for j in range(i*i,n+1,i):
p[j]=False
i+=1
p[0],p[1],prime=False,False,list()
for i in range(n+1):
if p[i]==True:
prime.append(i)
string,i='',0
while prime[i]<=n:
if n%prime[i]==0:
string=string+str(prime[i])+'x'
n=n/prime[i]
else:
i+=1
if len(string)==0:
return str(n)
return string[:-1]Bài 4: GCPD (Greatest Common Prime Divisor) được định nghĩa là số nguyên tố lớn nhất là ước của các số nguyên dương cho trước. Tìm GCPD của a và b nếu không tồn tại thì return -1
def Greatest_Common_Prime_Divisor(a,b):
n=min(a,b)
p,i=[True]*(n+1),2
while i*i<=n:
if p[i]==True:
for j in range(i*i,n+1,i):
p[j]=False
i+=1
p[0],p[1],prime=False,False,list()
for i in range(n+1):
if p[i]==True:
prime.append(i)
for i in reversed(prime):
if a%i==0 and b%i==0:
return i
return -1
