---
# System prepended metadata

title: Sàng nguyên tố

---

# Sàng nguyên tố
### 1. Lý thuyết

https://vi.wikipedia.org/wiki/S%C3%A0ng_Eratosthenes
![Animation_Sieb_des_Eratosthenes_(vi)](https://hackmd.io/_uploads/ryay0-92a.gif)

### 2. Giải thuật
- Ban đầu, giả sử tất cả các số từ 2 đều là số nguyên tố.
- Duyệt qua tất cả các số:
    - Nếu 1 số là số nguyên tố, đánh dấu tất cả các bội của số đó không phải là số nguyên tố.
- Code:
```python=
snt = [1]*(10**6+5)
def sieve():
    for i in range(2,(10**6+5)**0.5+1):
        if snt[i] == 1:
            for j in range(i*i,(10**6+5),i):
                snt[j] = 0
                
sieve()
k = 25
if snt[k]:
    print('k la so nguyen to')
else:
    print('k khong phai la so nguyen to')
```

### 3. Sửa bài

#### 1. Bài 1
- Sử dụng sàng nguyên tố tới 1e7
```python=
snt = [1]*(10**7+5)
snt[0] = 0
snt[1] = 0
def sieve():
    for i in range(2,int((10**7+5)**0.5)+1):
        if snt[i] == 1:
            for j in range(i*i,(10**7+5),i):
                snt[j] = 0
                
sieve()

n,m = map(int,input().split())
for i in range(n,m+1):
    if snt[i]:
        print(i)
```


#### 2. Bài 2
- Duyệt cơ bản và tìm ước cơ bản để tính


#### 3. Bài 3
- Sử dụng sàng khi tìm thấy ước ta đánh đánh dấu bội bằng cách cộng thêm ước đó vào tổng của bội
- ta không cần kiểm tra số nguyên tố

```python=
f = [1]*(10**6+5)
def sieve():
    for i in range(2,int((10**6+5))+1):
        for j in range(i*2,(10**6+5),i):
            f[j]+=i
            
sieve()
d = 0
l = int(input())
r = int(input())
for i in range(l,r+1):
    if f[i] > i:
        d+=1
print(d)
        
```


#### 4. Bài 4
```python=
f = [1]*(10**6+5)
def sieve():
    for i in range(2,int((5*10**6+5))+1):
        for j in range(i*2,(5*10**6+5),i):
            f[j]+=i
            
sieve()
d = 0
f[0] = 0
f[1] = 0
n = nhap n
a = nhap mang a
for i in a:
    if f[i] < i:
        d+=1
print(d)
        
```