Số học 2

Chuyên đề Số học 2: Khám phá nguyên tố, ước số và ứng dụng. Bài viết cung cấp kiến thức toán học cơ bản và nâng cao, cùng bài tập vận dụng hữu ích.

• Người hướng dẫn: Nguyễn Tiến Thành
• Trường học: Trường Thpt Chuyên Thái Bình
• Chuyên ngành: Số Học
• Đề tài: Số Nguyên Tố, Ước Số, Bội Số, Số Fibonacci, Số Catalan, Xử Lí Số Nguyên Lớn
• Loại tài liệu: Chuyên đề
• Năm xuất bản: 2019 - 2020
• Địa điểm: Thái Bình

Mục lục chi tiết

• MỞ ĐẦU
• 1. CHUYÊN ĐỀ CÁC BÀI TOÁN SỐ HỌC
• 1.1. Số nguyên tố
• 1.1.1. Định nghĩa
• 1.1.2. Kiểm tra tính nguyên tố theo định nghĩa
• 1.1.3. Kiểm tra số nguyên tố theo xác suất
• 1.1.4. Liệt kê các số nguyên tố trong đoạn [1,N]
• 1.1.5. Sử dụng sàng số nguyên tố sàng Eratosthene
• 1.2. ƯỚC SỐ, BỘI SỐ
• 1.2.1. Số các ước của một số
• 1.2.2. Ước chung lớn nhất của hai số
• 1.2.3. Bội chung nhỏ nhất của hai số
• 1.3. Dãy số Fibonacci
• 1.4. Dãy số CATALAN
• 1.5. Xử lí số nguyên lớn
• 1.5.1. Cộng 2 số nguyên lớn
• 1.5.2. Trừ 2 số nguyên lớn (Trừ số lớn cho số bé)
• 1.5.3. Nhân một số nguyên lớn với một nguyên số nhỏ
• 1.5.4. Nhân 2 số nguyên lớn
• 1.5.5. Chia số nguyên lớn cho số nguyên nhỏ
• 1.5.6. Chia hai số nguyên lớn
• 2. MỘT SỐ BÀI TẬP ÁP DỤNG
• 2.1. Bài 1. C11PNUM - Số nguyên tố.com/problems/C11PNUM/
• 2.2. Bài 2. C11PRIME - Số nguyên tố (Nguồn SPOJ) https://vn.com/problems/C11PRIME/
• 2.3. Bài 3. Số đặc biệt
• 2.4. Bài 4. PTIT017J - ACM PTIT 2017 J - Số các số không chia hết (Nguồn SPOJ) http://www.com/PTIT/problems/PTIT017J/
• 2.5. Bài 5. Bội chung nhỏ nhất
• 2.6. Bài 6. PTIT016A - ACM PTIT 2016 A - Bội số chung nhỏ nhất (Nguồn SPOJ) https://www.com/PTIT/problems/PTIT016A/

Tóm tắt

I. Số Nguyên Tố và Hợp Số Tổng Quan Ứng Dụng Chuyên Đề

Chuyên đề số học này tập trung vào các khái niệm cơ bản nhưng quan trọng về số nguyên tố và hợp số, đồng thời đi sâu vào các ứng dụng thực tế của chúng. Từ định nghĩa, cách kiểm tra tính nguyên tố, đến thuật toán sàng Eratosthenes, chuyên đề này cung cấp một nền tảng vững chắc cho việc giải quyết các bài toán số học phức tạp. Khám phá những bí mật ẩn sau những con số, từ những viên gạch cơ bản của số học đến những cấu trúc toán học tinh tế. Bài viết này không chỉ giới thiệu lý thuyết mà còn chú trọng vào việc áp dụng kiến thức vào giải quyết các bài toán số học. Ta đi từ những khái niệm như số nguyên tố, ước số, bội số đến những thuật toán hiệu quả như thuật toán Euclid để tìm ước chung lớn nhất và bội chung nhỏ nhất. Chuyên đề này không chỉ dành cho học sinh giỏi toán mà còn hữu ích cho bất kỳ ai muốn nâng cao khả năng tư duy logic và giải quyết vấn đề. Theo tài liệu gốc, "Trong nhiều bài toán Tin học, việc vận dụng kiến thức số học giúp đưa ra được những thuật toán tối ưu hơn."

1.1. Định nghĩa và tính chất cơ bản của số nguyên tố

Một số nguyên tố là một số tự nhiên lớn hơn 1 chỉ có hai ước số duy nhất là 1 và chính nó. Các số nguyên tố đóng vai trò quan trọng trong lý thuyết số vì chúng là các "viên gạch" xây dựng nên mọi số tự nhiên khác (ngoại trừ 1). Hợp số, ngược lại, là số tự nhiên lớn hơn 1 có nhiều hơn hai ước số. Việc hiểu rõ định nghĩa và tính chất của số nguyên tố là bước đầu tiên để khám phá thế giới số học.

Số học modulo cũng là một khái niệm liên quan, đặc biệt trong việc kiểm tra tính nguyên tố và giải các phương trình đồng dư. Định lý Fermat nhỏ, ví dụ, cung cấp một phương pháp kiểm tra tính nguyên tố dựa trên số học modulo. Ví dụ: Các số nguyên tố đầu tiên là 2, 3, 5, 7, 11, 13, 17, 19, 23...

1.2. Các phương pháp kiểm tra tính nguyên tố hiệu quả

Kiểm tra tính nguyên tố là một bài toán cơ bản trong số học. Phương pháp đơn giản nhất là thử chia số cần kiểm tra cho tất cả các số từ 2 đến căn bậc hai của nó. Nếu không chia hết cho số nào trong khoảng này, thì số đó là số nguyên tố. Tuy nhiên, phương pháp này không hiệu quả với các số lớn. Các phương pháp nâng cao hơn bao gồm kiểm tra theo xác suất (ví dụ, kiểm tra Miller-Rabin) và sử dụng số học modulo kết hợp với các định lý như định lý Fermat nhỏ. Theo tài liệu, có thể "Cải tiến kiểm tra tính nguyên tố của số N bằng cách kiểm tra xem N có chia hết cho số 2, số 3 và các số có dạng 6k 1 trong đoạn 5, N  ."

1.3. Sàng Eratosthenes Thuật toán liệt kê số nguyên tố trong phạm vi

Sàng Eratosthenes là một thuật toán cổ điển và hiệu quả để liệt kê tất cả các số nguyên tố nhỏ hơn hoặc bằng một số cho trước. Thuật toán hoạt động bằng cách loại bỏ dần các bội của các số nguyên tố, bắt đầu từ 2. Các số còn lại sau khi loại bỏ hết các bội chính là các số nguyên tố. Ưu điểm của sàng Eratosthenes là đơn giản và dễ cài đặt, đặc biệt hiệu quả khi cần liệt kê nhiều số nguyên tố trong một phạm vi nhất định. Ví dụ, sàng Eratosthenes có thể được sử dụng để tạo ra một bảng các số nguyên tố để sử dụng trong các ứng dụng khác. "void Eratosthene(int N) { int a[1000] = {0}; //Tạo mảng và gán tất cả bằng 0 for(int i = 2; ii <= N;i++) if(!a[i]) //Nếu là số nguyên tố //Duyệt các phần tử là bội số của i for(int j = ii; j <= N; j+=i) a[j]=1; //Đánh dấu các phần tử là bội số. //In các phần tử là số nguyên tố ra màn hình for (int i=2;i<=N;i++) if(!a[i]) printf("%d ",i); }"

II. Ước Số Bội Số và Các Thuật Toán Tìm Ước Chung Lớn Nhất

Ngoài số nguyên tố, ước số và bội số là những khái niệm quan trọng khác trong số học. Việc tìm ước chung lớn nhất (ƯCLN) và bội chung nhỏ nhất (BCNN) của hai hay nhiều số là một bài toán thường gặp, có nhiều ứng dụng trong thực tế. Thuật toán Euclid là một trong những thuật toán hiệu quả nhất để tìm ƯCLN của hai số. Hơn nữa, hiểu về ước số, bội số mở ra nhiều ứng dụng thú vị, từ việc phân tích thừa số nguyên tố đến giải các phương trình Diophantine. Các khái niệm ước chung, bội chung cũng đóng vai trò quan trọng. Tài liệu gốc cho biết "Ước số chung lớn nhất (USCLN) của hai số được tính theo thuật toán Euclid USCLN  a, b   USCLN b,  a mod b   ."

2.1. Số lượng và tổng các ước của một số cho trước

Số lượng và tổng các ước số của một số có thể được tính toán dễ dàng nếu biết phân tích thừa số nguyên tố của số đó. Nếu một số N có thể được phân tích thành N = a^i * b^j * ... * c^k, thì số lượng ước số của N là (i+1)(j+1)...(k+1), và tổng các ước số của N có thể được tính bằng công thức (1+a+a^2+...+a^i)(1+b+b^2+...+b^j)...(1+c+c^2+...+c^k). Ví dụ: Số 12 = 2^2 * 3^1 có (2+1)(1+1) = 6 ước số: 1, 2, 3, 4, 6, 12.

2.2. Thuật toán Euclid Cách tìm ước chung lớn nhất hiệu quả

Thuật toán Euclid là một phương pháp hiệu quả để tìm ước chung lớn nhất (ƯCLN) của hai số nguyên. Thuật toán dựa trên nguyên lý rằng ƯCLN của hai số không thay đổi nếu số lớn hơn được thay thế bằng hiệu của nó với số nhỏ hơn. Quá trình này lặp lại cho đến khi hai số bằng nhau, và số đó chính là ƯCLN. Phiên bản hiệu quả hơn của thuật toán sử dụng phép chia lấy dư thay vì phép trừ. Để có thể sử dụng hàm tìm UCLN trong C++ ta cần thêm thư viện algorithm. Ví dụ: int main(){ int a = 5, b = 9; printf("\ngcd(%d, %d) = %d", a, b, std::__gcd(a,b)); }

2.3. Mối liên hệ giữa ước chung lớn nhất và bội chung nhỏ nhất

Ước chung lớn nhất (ƯCLN) và bội chung nhỏ nhất (BCNN) có mối quan hệ mật thiết với nhau. Tích của hai số bằng tích của ƯCLN và BCNN của chúng. Công thức này có thể được sử dụng để tính BCNN nếu đã biết ƯCLN, hoặc ngược lại. Công thức tính BCNN (a, b) = (a * b) / ƯCLN (a, b). Theo tài liệu, "ab a BSCNN (a, b)   b USCLN (a, b) USCLN (a, b)"

III. Dãy Fibonacci và Catalan Ứng Dụng Trong Các Bài Toán

Dãy Fibonacci và Catalan là hai dãy số nổi tiếng trong toán học, xuất hiện trong nhiều lĩnh vực khác nhau, từ số học đến tổ hợp và khoa học máy tính. Dãy Fibonacci được định nghĩa bằng công thức truy hồi, trong khi dãy Catalan có công thức tổng quát phức tạp hơn. Cả hai dãy đều có nhiều tính chất thú vị và được áp dụng để giải quyết nhiều bài toán thực tế. Các số Fibonacci là đáp án của các bài toán như Bài toán cổ về sự sinh sản của các cặp thỏ...Dãy số CATALAN được xác định bởi công thức sau: Catalann  C2nn  với n ≥ 0.

3.1. Định nghĩa và các tính chất quan trọng của dãy Fibonacci

Dãy Fibonacci được định nghĩa bằng công thức truy hồi: F(0) = 0, F(1) = 1, và F(n) = F(n-1) + F(n-2) với n >= 2. Dãy số này có nhiều tính chất thú vị, bao gồm tỷ lệ giữa hai số liên tiếp tiến dần đến tỷ lệ vàng (golden ratio). Dãy Fibonacci xuất hiện trong nhiều lĩnh vực khác nhau, từ tự nhiên (ví dụ, số cánh hoa) đến tài chính (ví dụ, phân tích kỹ thuật). Một số phần tử đầu tiên của dãy số Fibonacci: n 0 1 2 3 4 5 6 … Fibonaccin 0 1 1 2 3 5 8 …

3.2. Ứng dụng của dãy Fibonacci trong các bài toán thực tế

Dãy Fibonacci có nhiều ứng dụng trong thực tế, bao gồm: (1) Bài toán về sự sinh sản của các cặp thỏ, (2) Đếm số cách lát gạch, (3) Tính số đường đi trên lưới, (4) Các bài toán tối ưu hóa, (5) Ứng dụng trong khoa học máy tính như thuật toán tìm kiếm Fibonacci. Các thuật toán dựa trên dãy Fibonacci có thể mang lại hiệu quả cao hơn so với các thuật toán truyền thống trong một số trường hợp nhất định. Ví dụ: đếm số cách xếp n-1 quân domino kích thước 2  1 phủ kín bảng có kích thước 2  (n  1).

3.3. Dãy số Catalan Khái niệm công thức và ứng dụng đa dạng

Dãy Catalan là một dãy số tự nhiên xuất hiện trong nhiều bài toán tổ hợp khác nhau. Số Catalan thứ n, ký hiệu là C_n, có thể được tính bằng công thức C_n = (2n)! / ((n+1)!n!). Dãy Catalan có nhiều ứng dụng, bao gồm: (1) Đếm số cách đặt dấu ngoặc đúng, (2) Đếm số cây nhị phân khác nhau, (3) Đếm số cách chia đa giác thành các tam giác. Một số phần tử đầu tiên của dãy số Catalan là: n 0 1 2 3 4 5 6 … Catalann 1 1 2 5 14 42 132 …

IV. Xử Lý Số Nguyên Lớn Các Thuật Toán Bài Toán Liên Quan

Trong nhiều bài toán số học và mật mã, chúng ta cần xử lý các số nguyên có kích thước rất lớn, vượt quá khả năng biểu diễn của các kiểu dữ liệu số nguyên thông thường. Việc xử lý các số nguyên lớn đòi hỏi các thuật toán đặc biệt để thực hiện các phép toán cộng, trừ, nhân, chia một cách hiệu quả. Xử lý số nguyên lớn bao gồm các phép tính như Cộng 2 số nguyên lớn, Trừ 2 số nguyên lớn, Nhân một số nguyên lớn với một nguyên số nhỏ, Nhân 2 số nguyên lớn và Chia số nguyên lớn cho số nguyên nhỏ. Các bài toán số học liên quan đến số học yêu cầu việc xử lý các phép tính trên các số lớn.

4.1. Thuật toán cộng trừ số nguyên lớn Chi tiết và tối ưu

Thuật toán cộng và trừ số nguyên lớn thường được thực hiện bằng cách biểu diễn số nguyên lớn dưới dạng một mảng các chữ số. Các chữ số được cộng hoặc trừ theo từng cặp, bắt đầu từ hàng đơn vị, và nhớ được chuyển sang hàng kế tiếp nếu cần thiết. Để tối ưu hiệu suất, có thể sử dụng các kỹ thuật như chia nhỏ số thành các khối lớn hơn và sử dụng các phép toán bit để tăng tốc độ tính toán. Bước 1: Chuẩn hóa hai xâu a, b để có độ dài bằng nhau. Bước 2: Duyệt từ cuối hai xâu về đầu xâu...

4.2. Thuật toán nhân chia số nguyên lớn Hiệu quả và phức tạp

Thuật toán nhân và chia số nguyên lớn phức tạp hơn so với cộng và trừ. Thuật toán nhân thường được thực hiện bằng cách nhân từng chữ số của số thứ nhất với toàn bộ số thứ hai, sau đó cộng các kết quả lại với nhau, tương tự như cách nhân tay thông thường. Thuật toán chia có thể được thực hiện bằng cách sử dụng thuật toán chia dài, hoặc bằng cách sử dụng các thuật toán chia nhanh hơn như thuật toán chia Newton. Phân tích thuật toán: Duyệt từ cuối xâu a về đầu xâu. - Tách từng phần tử của xâu a nhân với xâu b...

4.3. Ứng dụng của xử lý số nguyên lớn trong các bài toán mật mã

Xử lý số nguyên lớn đóng vai trò quan trọng trong nhiều hệ thống mật mã hiện đại, chẳng hạn như RSA và ECC. Các hệ thống này dựa trên độ khó của việc phân tích một số lớn thành các thừa số nguyên tố. Khả năng xử lý số nguyên lớn hiệu quả là yếu tố then chốt để đảm bảo tính bảo mật của các hệ thống này. Các phương trình Diophantine sử dụng số học modulo.

V. Bài Tập Ứng Dụng Chuyên Đề Số Học Nguyên Tố Ước Số

Để củng cố kiến thức và rèn luyện kỹ năng giải quyết bài toán số học, chuyên đề này cung cấp một loạt các bài tập ứng dụng, từ cơ bản đến nâng cao. Các bài tập này bao gồm kiểm tra tính nguyên tố, tìm ƯCLN và BCNN, giải phương trình Diophantine, và áp dụng các thuật toán xử lý số nguyên lớn. Việc giải các bài tập này giúp người học hiểu sâu hơn về các khái niệm và kỹ thuật đã học, đồng thời phát triển khả năng tư duy logic và sáng tạo. Các bài tập áp dụng là: C11PNUM - Số nguyên tố, C11PRIME - Số nguyên tố , Số đặc biệt, PTIT017J - ACM PTIT 2017 J - Số các số không chia hết...

5.1. C11PNUM Số nguyên tố Tìm tích K số nguyên tố liên tiếp

Bài toán yêu cầu tìm số nguyên lớn nhất không vượt quá N và là tích của K số nguyên tố liên tiếp. Để giải bài toán này, cần sử dụng thuật toán sàng Eratosthenes để liệt kê các số nguyên tố trong một phạm vi nhất định, sau đó tính các tích K số nguyên tố liên tiếp và tìm số lớn nhất thỏa mãn điều kiện. Bài này đòi hỏi kiến thức về số nguyên tố.

5.2. PTIT017J ACM PTIT 2017 J Số các số không chia hết

Bài toán yêu cầu tìm số lượng các số nhỏ hơn hoặc bằng N không chia hết cho bất kỳ số nào trong một tập hợp các số cho trước. Để giải bài toán này, cần sử dụng nguyên lý bù trừ. Đầu tiên, tính số lượng các số chia hết cho từng số trong tập hợp, sau đó tính số lượng các số chia hết cho các cặp số, các bộ ba số, v.v. Cuối cùng, áp dụng công thức bù trừ để tính số lượng các số không chia hết cho bất kỳ số nào. Bài này đòi hỏi kiến thức về toán rời rạc.

5.3. CATALAN Dãy số Catalan Tìm thứ tự và dãy số tương ứng

Bài toán yêu cầu tìm thứ tự của một dãy Catalan cho trước, hoặc tìm dãy Catalan có thứ tự cho trước. Để giải bài toán này, cần hiểu rõ về cấu trúc của dãy Catalan và sử dụng các thuật toán đệ quy hoặc quy hoạch động. Nếu gọi A[i,j] là giá trị lớn nhất của BSCNN khi phân tích i thành tổng của j số tự nhiên...

VI. Hướng Nghiên Cứu Phát Triển Chuyên Đề Số Học Ước Số

Chuyên đề số học này cung cấp một nền tảng vững chắc cho việc nghiên cứu và phát triển các lĩnh vực liên quan. Các hướng nghiên cứu tiềm năng bao gồm: (1) Phát triển các thuật toán hiệu quả hơn để kiểm tra tính nguyên tố và phân tích thừa số nguyên tố, (2) Nghiên cứu các tính chất mới của các dãy số đặc biệt như Fibonacci và Catalan, (3) Áp dụng số học vào các lĩnh vực mới như mật mã học và khoa học dữ liệu.

6.1. Các bài toán mở và hướng nghiên cứu mới trong lý thuyết số

Lý thuyết số là một lĩnh vực rộng lớn và phức tạp, với nhiều bài toán mở chưa được giải quyết. Các bài toán này bao gồm giả thuyết Riemann, bài toán Goldbach, và bài toán về sự tồn tại của vô số cặp số nguyên tố sinh đôi. Việc giải quyết các bài toán này đòi hỏi sự kết hợp giữa kiến thức lý thuyết sâu rộng và kỹ năng giải quyết vấn đề sáng tạo.

6.2. Ứng dụng của số học trong mật mã học và an toàn thông tin

Số học đóng vai trò then chốt trong mật mã học và an toàn thông tin. Các hệ thống mật mã hiện đại dựa trên độ khó của các bài toán số học, chẳng hạn như phân tích thừa số nguyên tố và bài toán logarit rời rạc. Việc nghiên cứu và phát triển các thuật toán số học mới có thể dẫn đến các hệ thống mật mã an toàn hơn và hiệu quả hơn.

6.3. Kết nối giữa số học và các lĩnh vực toán học khác

Số học có mối liên hệ mật thiết với nhiều lĩnh vực toán học khác, chẳng hạn như đại số, hình học và giải tích. Các khái niệm và kỹ thuật từ số học có thể được áp dụng để giải quyết các bài toán trong các lĩnh vực này, và ngược lại. Việc khám phá các kết nối này có thể dẫn đến những khám phá toán học mới và thú vị.

Trích đoạn nội dung tài liệu

Mở đầu, Nội dung và Kết luận. Trong phần Nội dung (và cũng là phần chính của chuyên đề) chúng tôi đề cập tới các vấn đề chính: Số nguyên tố, Ước số, Bội số, Số Fibonacci, Số Catalan, Xử lí số nguyên lớn,. Do chuyên đề này là các bài toán số học nên kiến thức cơ sở sẽ được ứng dụng trong từng bài tập cụ thể. Về mặt lí thuyết số học có rất nhiều tài liệu đã trình bày, ngay cả trong cuốn tài liệu giáo khoa chuyên Tin quyển 1 đã hệ thống rất cụ thể.

Chuyên đề là sự sưu tầm, chọn lọc, sắp xếp và hệ thống những vấn đề cơ bản của các bài toán số học theo một mạch kiến thức nhất định dựa trên một số nguồn tài liệu đã có. Cùng với đó, chúng tôi có đưa ra những phân tích, đánh giá để làm sáng tỏ cho mỗi vấn đề được đề cập tới. Với cách tiếp cận mở như vậy, hy vọng chuyên đề này sẽ giúp các em học sinh có được một hệ thống những kiến thức cần thiết, các thầy cô giáo có một chuyên đề chuyên môn bổ ích và thiết thực. Số nguyên tố 1.

Định nghĩa Một số tự nhiên p (p>1) là số nguyên tố nếu p có đúng hai ước số là 1 và p. Ví dụ các số nguyên tố: 2, 3, 5, 7, 11, 13, 17, 19, 23, … 1. Kiểm tra tính nguyên tố theo định nghĩa. Ý tưởng chính để kiểm tra số nguyên dương N (N>1) có là số nguyên tố hay không, ta kiểm tra xem có tồn tại số nguyên k (2  k  N ) mà k là ước của N (N chia hết cho k) thì N không phải là số nguyên tố, ngược lại N là số nguyên tố.

bool IsPrime(int N) { if (N < 2) return flase; for(int i = 2; i < sqrt(N); i++) if(N%i==0) return flase; return true; } Tuy nhiên ta thấy cách này không hiệu quả khì thời gian kiểm tra lâu. Cải tiến kiểm tra tính nguyên tố của số N bằng cách kiểm tra xem N có chia hết cho số 2, số 3 và các số có dạng 6k 1 trong đoạn 5, N . Kiểm tra số nguyên tố theo xác suất Các khái niệm, tính chất của đồng dư thức, và định lý cần nhớ như định lý Ferma. Ở đây tôi đề cập đến định lý Ferma nhỏ và tổng quát hóa của định lý Ferma: Định lý Ferma nhỏ Nếu p là một số nguyên tố, thì với số nguyên a bất kỳ, ap-a sẽ chia hết cho p.

Định lý Fermat còn được tổng quát hóa bởi Định lý Euler: với modulo n bất kỳ và số nguyên a bất kỳ là số nguyên tố cùng nhau với n, ta có: a ( n )  1(mod n). Trong đó  (n) là kí hiệu của hàm phi Euler đếm số các số nguyên giữa 1 và n nguyên tố cùng nhau với n. Đây là tổng quát hóa của định lý nhỏ Fermat vì nếu n=p là số nguyên tố thì  ( p)  n  1. Liệt kê các số nguyên tố trong đoạn [1,N].

Thử lần lượt các số m trong đoạn [1,N], rồi kiểm tra tính nguyên tố của m. void OutPrime(int N) { for(int i = 2; i <= N; i++) if(IsPrime(i)) printf("%d\t", i); } Ta thấy: Cách này đơn giản nhưng chạy chậm, để cải tiến có thể sử dụng các tính chất của số nguyên tố để loại trước những số không phải là số nguyên tố và không cần phải kiểm tra trước các số này. Sử dụng sàng số nguyên tố sàng Eratosthene. Giả sử tất cả đều là số nguyên tố, trước tiên xóa bỏ số 1 ra khỏi tập các số nguyên tố.

Số tiếp theo số 1 là số 2, là số nguyên tố, xóa tất cả các bội số của 2 ra khỏi bảng, xét lên 3, loại tất cả các bội số của 3,… thuật toán tiếp tục cho đến khi gặp số nguyên tố lớn hơn n thì dừng lại. Kết thúc quá trình các số chưa bị loại là số nguyên tố. 4 void Eratosthene(int N) { int a[1000] = {0}; //Tạo mảng và gán tất cả bằng 0 for(int i = 2; i*i <= N;i++) if(!a[i]) //Nếu là số nguyên tố //Duyệt các phần tử là bội số của i for(int j = i*i; j <= N; j+=i) a[j]=1; //Đánh dấu các phần tử là bội số. //In các phần tử là số nguyên tố ra màn hình for (int i=2;i<=N;i++) if(!a[i]) printf("%d ",i); } 2.

ƯỚC SỐ, BỘI SỐ 2. Số các ước của một số Giả sử N được phân tích thành thừa số nguyên tố như sau: N  ai  b j .  c k Ước số của N có dạng: a p  b q . Do đó: Số các ước của N là:  i  1   j  1 .

Ví dụ: N  100  22  52 , số các ước của 100 là:  2  1 2  1  9 (các ước của số đó là: 1, 2, 3, 4, 5, 10, 20, 50, 100). Tổng các ước của một số N  ai  b j .  a 1 b 1 c 1 (231  1) (311  1) Ví dụ: Tổng các ước của 24 là:   60 2 1 3 1 2. Ước chung lớn nhất của hai số Ước số chung lớn nhất (USCLN) của hai số được tính theo thuật toán Euclid USCLN  a, b   USCLN b,  a mod b  .

int gcd(int a, int b) { int tmp; while(b != 0) { tmp = a % b; a = b; b = tmp; } return a; } Chú ý: Để có thể sử dụng hàm tìm UCLN trong C++ ta cần thêm thư viện algorithm. Ví dụ: int main(){ int a = 5, b = 9; printf("\ngcd(%d, %d) = %d", a, b, std::__gcd(a,b)); } 2. Bội chung nhỏ nhất của hai số Bội số chung nhỏ nhất (BSCNN) của hai số được tính theo công thức: ab a BSCNN (a, b)   b USCLN (a, b) USCLN (a, b) 6 3. Dãy số Fibonacci Dãy số Fibonacci được xác định bởi các công thức sau:  F0  0   F1  1 F  F  F  n n 1 n  2 với n ≥ 2 Một số phần tử đầu tiên của dãy số Fibonacci: n 0 1 2 3 4 5 6 … Fibonaccin 0 1 1 2 3 5 8 … Số Fibonacci là đáp án của các bài toán: a) Bài toán cổ về sự sinh sản của các cặp thỏ với các giả thiết như sau: - Các con thỏ không bao giờ chết; - Hai tháng sau khi ra đời, mỗi cặp thỏ mới sẽ sinh ra một cặp thỏ con (một đực, một cái); - Khi đã sinh con rồi thì cứ mỗi tháng tiếp theo chúng lại sinh được một cặp con mới.

Giả sử từ đầu tháng 1 có một cặp mới thì đến giữa tháng thứ n sẽ có bao nhiêu cặp? b) Đếm số cách xếp n-1 quân domino kích thước 2  1 phủ kín bảng có kích thước 2  (n  1). Hàm tính số Fibonaci thứ n bằng phương pháp lặp sử dụng công thức Fn  Fn1  Fn2 với n  2 và F0  0, F1  1. Dãy số CATALAN Số Catalan được xác định bởi công thức sau: 1 (2n)! Catalann  C2nn  với n ≥ 0. n 1 (n  1)!n ! Một số phần tử đầu tiên của dãy số Catalan là: n 0 1 2 3 4 5 6 … Catalann 1 1 2 5 14 42 132 … Số Catalan là đáp án của các bài toán: a) Có bao nhiêu cách khác nhau đặt n dấu ngoặc mở và n dấu ngoặc đóng đúng đắn? Ví dụ: n=3 ta có 5 cách sau: ((())), (()()), (())(), ()(()), ()()() b) Có bao nhiêu cây nhị phân khác nhau có đúng n+1 lá? Ví dụ: n=3 c) Cho một đa giác lồi (n+2) đỉnh, ta chia thành các tam giác bằng nhau vẽ các đường chéo không cắt nhau trong đa giác.

Hỏi có bao nhiêu cách chia như vậy? 8 Ví dụ: n=4 5. Xử lí số nguyên lớn 5. Cộng 2 số nguyên lớn Phân tích thuật toán - Bước 1: Chuẩn hóa hai xâu a, b để có độ dài bằng nhau. Nếu xâu nào có độ dài ngắn hơn thì thêm các ‘0’ vào đầu xâu đó.

- Bước 2: Duyệt từ cuối hai xâu về đầu xâu: + Tạo xâu kết quả c=a; + Tách từng phần tử của hai xâu chuyển sang kiểu số; + Tính tổng: tổng = số 1 + số 2 + nhớ (ban đầu nhớ bằng 0); nhớ = tổng / 10; tổng = tổng % 10; + Chuyển đổi giá trị tổng tính được sang ký tự rồi gán vào xâu kết quả. + Lưu ý cộng thêm giá trị nhớ lần cuối nếu nhớ khác ‘0’. Chương trình tham khảo string Congxau(string a, string b) { string c; long n1=a. Trừ 2 số nguyên lớn (Trừ số lớn cho số bé) Phân tích thuật toán - Bước 1: Chuẩn hóa hai xâu a, b để có độ dài bằng nhau.

Nếu xâu nào có độ dài ngắn hơn thì thêm các ‘0’ vào đầu xâu đó. - Bước 2: Duyệt từ cuối hai xâu về đầu xâu: + Tạo xâu kết quả c=a; + Tách từng phần tử của hai xâu chuyển sang kiểu số; + Tính hiệu: hiệu = số 1 - số 2 - mượn (ban đầu mượn bằng 0); Nếu hiệu<0 thì {hiệu=hiệu+10; mượn=1;} Nếu hiệu>0 thì mượn =0; + Chuyển đổi giá trị hiệu tính được sang ký tự rồi gán vào xâu kết quả. + Xử lý xâu kết quả nếu xâu có độ dài lớn hơn 1 mà phần tử đầu tiên của mảng xâu là ‘0’. 10 Chương trình tham khảo string Truxau(string a, string b) { string c=""; long n1=a.

Nhân một số nguyên lớn với một nguyên số nhỏ Phân tích thuật toán - Bước 1: Duyệt từ cuối xâu số lớn về đầu xâu - Bước 2: + Tách từng phần tử của xâu chuyển sang kiểu số và tính tích: tích = số nhỏ * tg + nhớ (tg là số được tách từ xâu số lớn); nhớ = tích /10; Tích = tích % 10; + Chuyển đổi giá trị tích tính được sang ký tự rồi gán vào xâu kết quả. + Lưu ý cộng thêm giá trị nhớ lần cuối nếu nhớ khác ‘0’. 11 Chương trình tham khảo string Nhan1so(string a, int k) { string b; long i,Nho=0,Tich; for(i=a. Nhân 2 số nguyên lớn Phân tích thuật toán - Duyệt từ cuối xâu a về đầu xâu.

- Tách từng phần tử của xâu a nhân với xâu b (Thuật toán nhân với số nhỏ). - Cộng liên tiếp các kết quả thu được (lưu ý trước khi cộng 2 xâu thêm ký tự “0” vào sau xâu thứ 2). - Xử lý các ký tự “0” trước xâu sau khi cộng. Chương trình tham khảo string Nhanxau(string a, string b) { string x,Tg1="0",Tg2,c; long i,j=0; 12 for(i=b.length(),j,'0'); j++; c=Congxau(Tg1,Tg2); Tg1=c; } return c; } 5.