Skip to content

Latest commit

 

History

History
 
 

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 

Thừa số nguyên tố

Số nguyên tố là những số lớn hơn 1không thể chia hết cho những số khác. Các số nguyên tố đầu tiên : 2, 3, 5, 7, 11, 13, 17, 19,...

Nêú ta có thể tạo ra một số bằng cách nhân các số khác nhau lại thì số đó gọi là hợp số.

Composite numbers

Image source: Math is Fun

Thừa số nguyên tố là những số nguyên tố nhân với nhau để cho ra một số. Ví dụ 39 sẽ có các thừa số nguyên tố là 313. Một ví dụ khác là 15 có thừa số nguyên tố là 35.

Factors

Image source: Math is Fun

Tìm và đếm thừa số nguyên tố

Cách tiếp cận là chia số tự nhiên n cho các số từ i=2 cho đến i=n. Giá trị của n sẽ được ghi đè bời (n / i) cho mỗi lần lặp.

Độ phức tạp thời gian trong trường hợp xấu nhất là O (n) vì vòng lặp chạy từ i = 2 đến i = n. Độ phức tạp thời gian có thể được tối ưu hoá bằng cách giảm từ O (n) thàng O(sqrt(n)). Khi đó vòng lặp chỉ chạy từ i = 2 đến i = sqrt(n). Bởi vì khi i lớn hơn sqrt(n) thì sẽ không còn số nào để n chia hết ngoại trừ chính nó.

Công thức Hardy-Ramanujan để tính gần đúng và đếm thừa số nguyên tố

Năm 1917, một định lý được đưa ra bởi G.H Hardy và Srinivasa Ramanujan trong đó nói rằng bậc bình thường của số ω (n) của các thừa số nguyên tố riêng biệt của một số nlog (log (n)).

Nói một cách đại khái, điều này có nghĩa là hầu hết các số đều có số lượng các thừa số nguyên tố riêng biệt này.

Liên kết