• Xét ý tưởng của việc kiểm tra tính nguyên tó của một só Ta có nhận xét sau: Nếu một số nguyên dương $n$ là hợp số, tồn tại một số nguyên tố $p \le \sqrt{n}$ và $n$ chia hết cho $p$.
• Với ý tưởng này, ta sử dụng sàng nguyên tố đề tìm tất cả các số nguyên tố không vượt quá $\sqrt{r}$, và với hàm kiểm tra nguyên tố ta chỉ cần kiểm tra tính chia hết của một số cho các số nguyên tố này mà thôi. Điều này có thể giảm đáng kể độ phức tạp.

Độ phức tạp: (xấp xỉ) $O((r - l) \times \frac{\sqrt{r}}{log_2(r)} + \sqrt{r} \times log_2(log_2(n)))$, nhưng với hằng số $C$ khá nhỏ.

• Từ nhận xét cơ bản: nếu $n$ là một hợp số thì $n$ tồn tại một ước nguyên dương khác $1$ không vượt quá $\sqrt{n}$, ta có ý tưởng tương tự như sàng nguyên tố như sau: Với mọi $i$ từ $2$ đến $\sqrt{r}$, ta loại bỏ tất cả các bội của $i$ khỏi danh sách. Những số còn lại sẽ là các số nguyên tố.
• Để thực hiện hoá ý tưởng trên, ban đầu ta khởi tạo một mảng $check$ có $r - l$ phần tử với tất cả các phần tử đều là True. Nếu phần tử thứ $i$ được đánh dấu là hợp số, ta đặt $check[i - l]$ thành False. Như vậy, nếu $check[i] =$ True sau khi đánh dấu, ta kết luận $l + i$ là số nguyên tố.

Độ phức tạp: $O((r - l) \times log_2(r - l))$.