Viết chương trình để in ra màn hình các số nguyên tố từ 1 đến N, với N là số nguyên dương nhập vào từ bàn phím. P/s: nhập trên phần mềm python, viết lý thuyết + thực hành trên python và chụp màn hình kết quả)

Thuật toán Eratosthenes:

Theo thuật toán eratosthenes, ta sẽ chọn lần lượt các số nguyên tố (giả sử ban đầu, tất cả số đều là số nguyên tố) và loại bỏ bội của chúng (khi `m` là bội của `n` thì `m\vdotsn`). Sau khi kết thúc quá trình, các số còn lại là số nguyên tố.

Vì khi chọn một số `i`, ta sẽ loại từ `i^2` (do các bội trước đó của `i` đã bị các số nguyên tố trước nó loại) nên chỉ cần loại từ `2` đến `\sqrt{n}` là được.

Ví dụ: Ban đầu có `20` số, ta sẽ loại bỏ như sau: Bắt đầu từ `2` đến `4` (`\sqrt{n} ~~ 4.47`)

Chọn `2`: Loại `4`, `6`, `8`, `10`, `12`, `14`, `16`, `18`, `20`.

Chọn `3`: Loại `9`, `12`, `15`, `18`.

`4` Đã bị loại.

Kết thúc quá trình, các số còn lại là: `2`, `3`, `5`, `7`, `11`, `13`, `17`, `19`.

$\\$

Code tham khảo:

from math import sqrt
n = int(input('n = '))
a = [True] * (n+1)
a[0] = a[1] = False #0 và 1 không phải số nguyên tố
for i in range(2, int(sqrt(n))+1):
    if a[i]:
        for j in range(i**2, n+1, i):
            a[j] = False #Loại bỏ các bội của i
for i in range(n+1):
    if (a[i]):
        print(i, end=' ') #Xuất các số nguyên tố

$\\$

`\bb\color{green}{\text{@Daoanhviet96}}`