Thủ Thuật

Số nguyên tố và các vấn đề liên quan

Bạn đang xem: số nguyên tố và các vấn đề liên quan Tại Website saigonmetromall.com.vn

I. Số nguyên tố và Hợp số

1. Giới thiệu

Số nguyên tố là số nguyên dương lớn hơn 111 và chỉ có đúng hai ước là 111 và chính nó.

Hợp số, là các số nguyên dương lớn hơn 111 và có nhiều hơn hai ước.

Lấy ví dụ: 555 là một số nguyên tố, vì nó chỉ có đúng hai ước là 111 và 555. Ngược lại 101010 là một hợp số vì nó có bốn ước là 1,2,51, 2, 51,2,5 và 101010. Số nguyên tố và các vấn đề xoay quanh nó luôn là một chủ đề được yêu thích trong Toán học nói chung và lập trình thi đấu nói riêng.

2. Kiểm tra tính nguyên tố của một số

2.1. Giải thuật cơ sở

Ý tưởng ban đầu rất đơn giản: Ta duyệt qua tất cả các số nguyên từ 222 tới N−1,N – 1,N−1, nếu như có số nào là ước của NNN thì kết luận NNN không phải số nguyên tố. Giải thuật có độ phức tạp O(N)O(N)O(N).

bool

is_prime

(

int

N

)

{

if

(

N

<

2

)

return

false

;

for

(

int

i

=

2

;

i

<

N

;

++

i

)

if

(

N

%

i

==

0

)

return

false

;

return

true

;

}

2.2. Cải tiến:

Xuất phát từ nhận xét sau: Giả sử số nguyên dương NNN có ước là DDD (0

bool

is_prime

(

int

N

)

{

if

(

N

<

2

)

return

false

;

for

(

int

i

=

2

;

i

*

i

<=

N

;

++

i

)

if

(

N

%

i

==

0

)

return

false

;

return

true

;

}

II. Sàng lọc số nguyên tố Eratosthenes

1. Giới thiệu

Sàng Eratosthenes là một giải thuật cổ xưa do nhà Toán học người Hy Lạp Eratosthenes phát minh ra để tìm các số nguyên tố nhỏ hơn 100100100. Tương truyền, khi tìm ra thuật toán, ông đã lấy lá cọ và ghi tất cả các số từ 222 cho đến 100100100 lên đó, sau đó chọc thủng các hợp số và giữ nguyên các số nguyên tố. Bảng số nguyên tố còn lại trông rất giống một cái sàng. Do đó, nó có tên là sàng Eratosthenes.

Với sự phát triển của máy tính, sàng Eratosthenes trở thành một công cụ rất hữu dụng để tìm ra các số nguyên tố trong một khoảng nhất định, với điều kiện bộ nhớ có thể lưu trữ được.

2. Cài đặt giải thuật

Nguyên lý hoạt động của sàng Eratosthenes như sau: Xét các số nguyên tố từ 222 tới N,\sqrt{N},N​, với mỗi số nguyên tố ta sẽ đánh dấu các bội của nó mà lớn hơn nó đều là hợp số. Sau khi duyệt xong, tất cả các số chưa được đánh dấu sẽ là số nguyên tố. Dưới đây cài đặt sàng lọc các số nguyên tố từ 111 tới NNN.

void

eratosthenes_sieve

(

int

N

)

{

fill

(

is_prime

,

is_prime

+

1

+

N

,

true

)

;

is_prime

[

0

]

=

is_prime

[

1

]

=

false

;

for

(

int

i

=

2

;

i

*

i

<=

N

;

++

i

)

if

(

is_prime

[

i

]

)

for

(

int

j

=

i

*

i

;

j

<=

N

;

j

+=

i

)

is_prime

[

j

]

=

false

;

}

Bạn đọc có thể thắc mắc tại sao các bội của iii lại không bắt đầu từ 2.i2.i2.i. Lí do là vì, vòng lặp duyệt các số nguyên tố tăng dần, khi tới số nguyên tố iii thì các bội 2.i,3.i,…,(i−1).i2.i, 3.i,…, (i – 1).i2.i,3.i,…,(i−1).i đều đã bị loại đi trước đó bởi các số nguyên tố nhỏ hơn iii rồi. Cũng chính nhờ điều này nên vòng lặp bên ngoài chỉ cần duyệt từ 222 tới N\sqrt{N}N​, giúp giảm độ phức tạp của giải thuật đi nhiều.

Xem Thêm :  Hình nền trắng 2022 ❤️ 1001 ảnh nền trắng full hd đẹp

Đánh giá độ phức tạp giải thuật:

  • Với

    i=2i = 2

    i

    =

    2

    , vòng lặp bên trong lặp

    N2\frac{N}{2}

    2

    N

    lần.

  • Với

    i=3i = 3

    i

    =

    3

    , vòng lặp bên trong lặp

    N3\frac{N}{3}

    3

    N

    lần.

  • Với

    i=5i = 5

    i

    =

    5

    , vòng lặp bên trong lặp

    N5\frac{N}{5}

    5

    N

    lần.

    ……

    Tổng số lần lặp sẽ là

    N.(12+13+15+…)N.(\frac{1}{2}+\frac{1}{3}+\frac{1}{5}+…)

    N

    .

    (

    2

    1

    +

    3

    1

    +

    5

    1

    +

    )

    , độ phức tạp sẽ tiến tới

    O(N.log(N))O(N.log(N))

    O

    (

    N

    .

    l

    o

    g

    (

    N

    ))

    .

3. Sàng số nguyên tố trên đoạn

Ở một số trường hợp, người ta cần tìm các số nguyên tố trên đoạn [L,R][L, R][L,R] cho trước và RRR có thể lên tới 1012,10^{12},1012, với điều kiện có thể tạo được một mảng có độ dài (R−L+1)(R – L + 1)(R−L+1).

Ý tưởng giải thuật như sau: Sàng lọc trước một mảng gồm các số nguyên tố trong đoạn [2…R][2…\sqrt{R}][2…R​], sau đó duyệt qua các số nguyên tố này, loại bỏ các bội của chúng nằm trong đoạn [L,R][L, R][L,R]. Code dưới đây cải tiến một chút để bỏ bớt bước tạo mảng số nguyên tố trong đoạn [2…R],[2…\sqrt{R}],[2…R​], nhằm tiết kiệm thời gian chạy.

void

range_eratosthenes

(

int

L

,

int

R

)

{

int

range

=

R

-

L

+

1

;

fill

(

is_prime

,

is_prime

+

1

+

range

,

true

)

;

for

(

long

long

i

=

2

;

i

*

i

<=

R

;

++

i

)

for

(

long

long

j

=

max

(

i

*

i

,

(

L

+

i

-

1

)

/

i

*

i

)

;

j

<=

R

;

j

+=

i

)

is_prime

[

j

-

L

]

=

false

;

if

(

L

==

1

)

is_prime

[

0

]

=

false

;

}

Như vậy với một số XXX trong đoạn [L,R],X[L, R], X[L,R],X là số nguyên tố khi và chỉ khi is_prime[X−L]=true\text{is\_prime}[X – L]=trueis_prime[X−L]=true. Thuật toán có độ phức tạp là O((R−L+1).log(R)+R)O((R – L + 1).log(R) + \sqrt{R})O((R−L+1).log(R)+R​). Trên thực tế nó chạy khá nhanh.

III. Phân tích thừa số nguyên tố

Vấn đề phân tích thừa số nguyên tố cũng khá được quan tâm trong lập trình thi đấu, và nó còn có một số ứng dụng khác trong số học. Dưới đây chúng ta sẽ xem xét vài phương pháp phân tích thừa số nguyên tố thường dùng.

1. Giải thuật cơ sở

Ta xét mọi số nguyên tố bắt đầu từ 2,2,2, nếu NNN chia hết cho số nguyên tố PPP thì chia NNN cho PPP tới khi không thể chia hết nữa, rồi tăng PPP lên và lặp lại công việc tới khi N=1N=1N=1. Trên thực tế thừa số nguyên tố chính là thành phần cấu tạo nên một ước của N,N,N, do đó khi tách hết một thừa số nguyên tố XXX khỏi NNN thì NNN sẽ không thể chia hết cho các bội lớn hơn XXX nữa.

Cài đặt:

vector 

<

int

>

extract

(

int

N

)

{

int

p

=

2

;

vector

<

int

>

prime_factor

;

while

(

N

>

1

)

{

while

(

N

%

p

==

0

)

{

prime_factor

.

push_back

(

p

)

;

N

/=

p

;

}

++

p

;

}

return

prime_factor

;

}

2. Cải tiến lần 1

Xuất phát từ nhận xét sau: Không thể xảy ra trường hợp mọi thừa số nguyên tố của NNN đều lớn hơn N,\sqrt{N},N​, do đó chúng ta chỉ cần xét các ước của NNN từ 222 tới N\sqrt{N}N​ và chia dần NNN cho các ước của nó tới khi NNN bằng 111. Nếu không thể tìm được ước nào từ 222 tới N\sqrt{N}N​ thì NNN phải là một số nguyên tố. Độ phức tạp giải thuật là O(N)O(\sqrt{N})O(N​).

Cài đặt:

vector 

<

int

>

extract

(

int

N

)

{

vector

<

int

>

prime_factor

;

for

(

int

i

=

2

;

i

*

i

<=

N

;

++

i

)

while

(

N

%

i

==

0

)

{

prime_factor

.

push_back

(

i

)

;

N

/=

i

;

}

if

(

N

>

1

)

prime_factor

.

push_back

(

i

)

;

return

prime_factor

;

}

3. Phân tích thừa số nguyên tố bằng sàng Eratosthenes:

Từ hai giải thuật trên ta thấy: Ở mỗi bước phân tích cần tìm ra ước nguyên tố nhỏ nhất của NNN rồi chia NNN cho ước đó. Ta sẽ thay đổi sàng Eratosthenes đi một chút để lấy được ngay ước nguyên tố nhỏ nhất của NNN trong O(1)O(1)O(1) ở mỗi bước phân tích, điều này sẽ giúp giảm thời gian chạy đi đáng kể.

Cài đặt:

void

eratosthenes_sieve

(

int

N

)

{

fill

(

smallest_divisor

+

1

,

smallest_divisor

+

1

+

N

,

0

)

;

fill

(

is_prime

,

is_prime

+

1

+

N

,

true

)

;

is_prime

[

0

]

=

is_prime

[

1

]

=

false

;

for

(

int

i

=

2

;

i

*

i

<=

N

;

++

i

)

if

(

is_prime

[

i

]

)

for

(

int

j

=

i

*

i

;

j

<=

N

;

j

+=

i

)

{

is_prime

[

j

]

=

false

;

if

(

smallest_divisor

[

j

]

==

0

)

smallest_divisor

[

j

]

=

i

;

}

for

(

int

i

=

2

;

i

<=

N

;

++

i

)

if

(

is_prime

[

i

]

)

smallest_divisor

[

i

]

=

i

;

}

vector

<

int

>

extract

(

int

N

)

{

eratosthenes_sieve

(

maxN

)

;

vector

<

int

>

prime_factor

;

while

(

N

>

1

)

{

int

p

=

smallest_divisor

[

N

]

;

prime_factor

.

push_back

(

p

)

;

N

/=

p

;

}

return

prime_factor

;

}

Mặc dù việc thực hiện sàng Eratosthenes vẫn mất O(N.logN),O(N.logN),O(N.logN), tuy nhiên thao tác phân tích một số PPP thành thừa số nguyên tố chỉ mất độ phức tạp O(logP)O(logP)O(logP). Điều này sẽ rất có lợi trong các bài toán phải phân tích thừa số nguyên tố nhiều lần.

4. Đếm số ước của một số nguyên

Giả sử ta phân tích được NNN thành các thừa số nguyên tố ở dạng:

N=p1k1×p2k2×…×pmkmN=p_1^{k_1}\times p_2^{k_2}\times … \times p_m^{k_m}
N=p1k1​​×p2k2​​×…×pmkm​​

Các ước số của NNN sẽ phải có dạng:

p1r1×p2r2×…×pmrmp_1^{r_1}\times p_2^{r_2}\times …\times p_m^{r_m}
p1r1​​×p2r2​​×…×pmrm​​

với 0≤r1≤k1,0≤r2≤k2,…,0≤rm≤km0 \le r_1 \le k_1, 0 \le r_2 \le k_2,…, 0 \le r_m \le k_m0≤r1​≤k1​,0≤r2​≤k2​,…,0≤rm​≤km​.

Theo nguyên lý nhân, ta thấy: r1r_1r1​ có k1+1k_1 + 1k1​+1 cách chọn, r2r_2r2​ có k2+2k_2 + 2k2​+2 cách chọn,…, rmr_mrm​ có km+1k_m + 1km​+1 cách chọn. Như vậy số lượng ước của NNN sẽ được tính theo công thức:

FN=(k1+1)×(k2+1)×…×(km+1)F_N=(k_1+1)\times (k_2+1) \times … \times (k_m+1)
FN​=(k1​+1)×(k2​+1)×…×(km​+1)

Từ đây, ta có ý tưởng đếm số ước của một số nguyên dương N như sau:

  • Phân tích

    NN

    N

    thành thừa số nguyên tố.

  • Đặt một biến

    cnt_x\text{cnt\_x}

    cnt_x

    là số lần xuất hiện của thừa số nguyên tố

    xx

    x

    trong phân tích của

    NN

    N

    . Ta vừa phân tích

    NN

    N

    vừa cập nhật số lượng thừa số nguyên tố lên biến

    cnt_x\text{cnt\_x}

    cnt_x

    .

Cài đặt:

int

count_divisors

(

int

N

)

{

int

total_divisor

=

1

;

for

(

int

i

=

2

;

i

*

i

<=

N

;

++

i

)

{

int

cnt

=

0

;

while

(

N

%

i

==

0

)

{

++

cnt

;

N

/=

i

;

}

total_divisors

*=

(

cnt

+

1

)

;

}

if

(

N

>

1

)

total_divisors

*=

2

;

return

total_divisors

;

}

Bạn đọc hãy tự suy nghĩ thêm cách sử dụng sàng Eratosthene để đếm số ước của số nguyên dương N,N,N, sẽ rất hữu dụng trong các bài toán cần đếm nhanh số ước của NNN.

5. Tính tổng các ước số nguyên dương của một số nguyên dương

Định lý: Nếu một số nguyên dương NNN khi phân tích ra thừa số nguyên tố có dạng:

N=p1k1×p2k2×…×pmkm (ki≠0;∀i:1≤i≤m)N=p_1^{k_1}\times p_2^{k_2}\times … \times p_m^{k_m} \text{ } (k_i \ne 0; \forall i: 1 \le i \le m)N=p1k1​​×p2k2​​×…×pmkm​​ (ki​=0;∀i:1≤i≤m) thì tổng các ước nguyên dương của nó được tính theo công thức:

σ(N)=∏i=1k(pimi+1pi−1)\sigma(N) = \prod_{i = 1}^k (\frac{p_i^{m_i + 1}}{p_i – 1})
σ(N)=i=1∏k​(pi​−1pimi​+1​​)

Chứng minh: Các ước số của NNN sẽ phải có dạng:

p1r1×p2r2×…×pmrmp_1^{r_1}\times p_2^{r_2}\times …\times p_m^{r_m}
p1r1​​×p2r2​​×…×pmrm​​

với 0≤r1≤k1,0≤r2≤k2,…,0≤rm≤km0 \le r_1 \le k_1, 0 \le r_2 \le k_2,…, 0 \le r_m \le k_m0≤r1​≤k1​,0≤r2​≤k2​,…,0≤rm​≤km​.

→\rightarrow→ Tổng các ước của NNN là:

σ(N)=∑r1=0k1∑r2=0k2⋯∑rm=0km(p1r1×p2r2×⋯×pmrm=∑r1=0k1p1r1×∑r2=0k2p2r2×⋯×∑rm=0kmpmrm (1)\sigma(N) = \sum_{r_1=0}^{k_1} \sum_{r_2=0}^{k_2} \cdots \sum_{r_m = 0}^{k_m} (p_1^{r_1} \times p_2^{r_2} \times \cdots \times p_m^{r_m} = \sum_{r_1=0}^{k_1} p_1^{r_1} \times \sum_{r_2=0}^{k_2} p_2^{r_2} \times \cdots \times \sum_{r_m=0}^{k_m} p_m^{r_m} \ (1)σ(N)=∑r1​=0k1​​∑r2​=0k2​​⋯∑rm​=0km​​(p1r1​​×p2r2​​×⋯×pmrm​​=∑r1​=0k1​​p1r1​​×∑r2​=0k2​​p2r2​​×⋯×∑rm​=0km​​pmrm​​ (1)

Mà ta có công thức dãy cấp số nhân sau:

p0+p1+p2+…+pn=pn+1−1p−1 (2)p^0 + p^1 + p^2 +…+ p^n = \frac{p^{n + 1} – 1}{p – 1} \ (2)
p0+p1+p2+…+pn=p−1pn+1−1​ (2)

Từ (1)(1)(1) và (2)(2)(2), ta có:

σ(N)=p1k1+1−1p1−1×p2k2+1−1p2−1×⋯×pmkm+1−1pm−1\sigma(N) = \frac{p_1^{k_1 + 1} – 1}{p_1 – 1} \times \frac{p_2^{k_2 + 1} – 1}{p_2 – 1} \times \cdots \times \frac{p_m^{k_m + 1} – 1}{p_m – 1}
σ(N)=p1​−1p1k1​+1​−1​×p2​−1p2k2​+1​−1​×⋯×pm​−1pmkm​+1​−1​

Cài đặt:

int

exponentiation

(

int

A

,

int

B

)

{

if

(

B

==

0

)

return

1

;

int

half

=

exponentiation

(

A

,

B

/

2

)

;

if

(

B

&

1

)

return

half

*

half

*

A

;

else

return

half

*

half

;

}

int

get_sum_divisors

(

int

N

)

{

if

(

N

==

1

)

return

1

;

int

sum_divisor

=

1

;

for

(

int

i

=

2

;

i

*

i

<=

N

;

++

i

)

{

int

cnt

=

0

;

while

(

N

%

i

==

0

)

{

++

cnt

;

N

/=

i

;

}

if

(

cnt

!=

0

)

sum_divisors

*=

(

(

exponentiation

(

i

,

cnt

+

1

)

-

1

)

/

(

i

-

1

)

)

;

}

if

(

N

>

1

)

sum_divisors

*=

(

N

*

N

/

(

N

-

1

)

)

;

return

sum_divisors

;

}

Tương tự, bạn đọc hãy tự suy nghĩ cách cải tiến việc phân tích thừa số nguyên tố bằng sử dụng sàng lọc eratosthene, trong những bài toán multitest sẽ cực kỳ hữu dụng về mặt tối ưu thời gian chạy.

Tài liệu tham khảo:


Số nguyên tố – Bài 10 – Toán lớp 6 – Kết nối tri thức – Cô Vương Thị Hạnh (HAY NHẤT)


? Đăng ký khóa học của thầy cô VietJack giá từ 250k tại: https://bit.ly/30CPP9X.
?Tải app VietJack để xem các bài giảng khác của thầy cô. Link tải: https://vietjack.onelink.me/hJSB/30701ef0
☎️ Hotline hỗ trợ: 084 283 4585
Toán lớp 6 Kết nối tri thức Bài 10 Số nguyên tố
Số nguyên tố là bài học quan trọng chương trình học mới của Bộ Giáo dục Bộ sách Kết nối tri thức với cuộc sống Toán học 6. Trong bài giảng này, cô sẽ giúp các em tìm hiểu tất cả các kiến thức trọng tâm nhất bài học. Từ đó, các em sẽ giải các dạng bài tập từ cơ bản nhất đến nâng cao. Các em chú ý theo dõi bài học cùng cô nhé !
Đăng kí mua khóa học của cô tại: https://m.me/hoc.cung.vietjack
Học trực tuyến tại: https://khoahoc.vietjack.com/
Fanpage: https://www.facebook.com/hoc.cung.vietjack/
vietjack, ketnoitrithuctoan6, bai10
▶ Danh sách các bài học môn Toán học 6 Bộ Kết nối tri thức Cô Vương Thị Hạnh:
https://www.youtube.com/playlist?list=PL5q2T2FxzK7UAfEwKx5m8XO0Js0jO7LKr
▶ Danh sách các bài học môn Toán học 6 Bộ sách cánh diều Cô Vương Thị Hạnh:
https://www.youtube.com/playlist?list=PL5q2T2FxzK7XZMLZW_I11biKlf4VWlZv
▶ Danh sách các bài học môn Toán 6 Chân trời sáng tạo Cô Vương Thị Hạnh:
https://www.youtube.com/playlist?list=PL5q2T2FxzK7WTszGjUKfkg11CqrGSS6G
▶ Danh sách các bài học môn Ngữ văn 6 Bộ Kết nối tri thức Cô Trương San:
https://www.youtube.com/playlist?list=PL5q2T2FxzK7VyXID22unAmLSkaBYLTeyA
▶ Danh sách các bài giải SGK Tiếng anh 6 Bộ Kết nối tri thức Cô Nguyễn Minh Hiền:
https://www.youtube.com/playlist?list=PL5q2T2FxzK7U4cqa74xBx0danckFmdp35
▶ Danh sách các bài giải SGK Tiếng anh 6 Bộ Kết nối tri thức Cô Nguyễn Thanh Hoa:
https://www.youtube.com/playlist?list=PL5q2T2FxzK7UoG41JyAIZjZPUiAXDZfgQ
▶ Danh sách các bài giải SGK Khoa học tự nhiên 6 Chân trời sáng tạo:
https://www.youtube.com/playlist?list=PL5q2T2FxzK7Vg4WIqTF20Dj8xa9sw3d
▶ Danh sách các bài giải SGK Khoa học tự nhiên 6 Kết nối:
https://www.youtube.com/playlist?list=PL5q2T2FxzK7XSSVOien0bQiYtnYM9Ertg
▶ Danh sách các bài giải SGK Khoa học tự nhiên 6 Cánh diều:
https://www.youtube.com/playlist?list=PL5q2T2FxzK7VnkOb_wCN3jyRwNbGlLbq
▶ Danh sách các bài giải SBT Khoa học tự nhiên 6 Kết nối:
https://www.youtube.com/playlist?list=PL5q2T2FxzK7Ww7BMk71RpewZmfDAMb1
▶ Danh sách các bài giải SBT Khoa học tự nhiên 6 Cánh diều:
https://www.youtube.com/playlist?list=PL5q2T2FxzK7WBP061NBRBZl1A4XdzA1d0
▶ Danh sách các bài giải SGK Toán học 6 Bộ sách Cánh diều Cô Nguyễn Hà Nguyên:
https://www.youtube.com/playlist?list=PL5q2T2FxzK7Wv53k7F79jQtA91rU0AxYt
▶ Danh sách các bài giải SGK Toán học 6 Bộ Kết nối tri thức Cô Hoàng Thanh Xuân:
https://www.youtube.com/playlist?list=PL5q2T2FxzK7Ux3WiZueloqyE2rDRCnZQd
▶ Danh sách các bài giải SGK Toán học 6 Bộ Kết nối tri thức Cô Minh Nguyệt:
https://www.youtube.com/playlist?list=PL5q2T2FxzK7X0xXAx3yd2Qu4p8YleIYy

Xem thêm bài viết thuộc chuyên mục: Thủ Thuật
Xem thêm bài viết thuộc chuyên mục: Thủ Thuật
Xem Thêm :  Hướng dẫn chi tiết cách vẽ xe tăng đơn giản với 9 bước cơ bản

Related Articles

Back to top button