Số nguyên tố là những số lớn hơn 1 và khô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ố.
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à 3 và 13. Một ví dụ khác là 15 có thừa số nguyên tố là 3 và 5.
Image source: Math is Fun
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ó.
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ố n là log (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.