Thuật toán sàng nguyên tố trong C#

Để tìm tất cả các số nguyên tố trong một khoảng giá trị cho trước, ta có thể sử dụng thuật toán Sàng Eratosthenes.

Thuật toán Sàng Eratosthenes hoạt động như sau:

• Bắt đầu với một danh sách tất cả các số nguyên từ 2 đến n, với n là số lớn nhất trong khoảng giá trị cho trước.
• Chọn số đầu tiên trong danh sách, nó là số nguyên tố.
• Loại bỏ tất cả các bội số của số nguyên tố đó ra khỏi danh sách.
• Lặp lại bước 2 và 3 cho đến khi không còn số nào trong danh sách.

Dưới đây là mã C# cho thuật toán sàng nguyên tố:

using System;

class Program {
    static void Main(string[] args) {
        int start = 2; // Số đầu tiên trong khoảng giá trị
        int end = 100; // Số cuối cùng trong khoảng giá trị

        // Khởi tạo mảng lưu trữ tất cả các số trong khoảng giá trị
        bool[] primes = new bool[end + 1];

        // Gán tất cả các giá trị trong mảng về true ban đầu
        for (int i = start; i <= end; i++) {
            primes[i] = true;
        }

        // Áp dụng thuật toán sàng nguyên tố để loại bỏ các số không phải là số nguyên tố
        for (int i = start; i * i <= end; i++) {
            if (primes[i]) {
                for (int j = i * i; j <= end; j += i) {
                    primes[j] = false;
                }
            }
        }

        // In ra tất cả các số nguyên tố trong khoảng giá trị
        for (int i = start; i <= end; i++) {
            if (primes[i]) {
                Console.Write(i + " ");
            }
        }
    }
}

Trong đoạn mã này, chúng ta sử dụng một mảng boolean để lưu trữ tất cả các số trong khoảng giá trị, với mỗi phần tử trong mảng tương ứng với một số nguyên dương. Nếu giá trị tại phần tử i là true, thì số nguyên dương i là số nguyên tố; ngược lại, nếu giá trị tại phần tử i là false, thì số nguyên dương i không phải là số nguyên tố.

Chúng ta sử dụng một vòng lặp để khởi tạo tất cả các giá trị trong mảng là true ban đầu. Sau đó, chúng ta sử dụng một vòng lặp khác để áp dụng thuật toán sàng nguyên tố, loại bỏ các số không phải là số nguyên tố khỏi danh sách. Trong vòng lặp này, ta bắt đầu từ số đầu tiên trong danh sách (tức là số 2), và loại bỏ tất cả các bội số của số đó ra khỏi danh sách bằng cách gán giá trị false cho các phần tử tương ứng trong mảng.

Cuối cùng, ta sử dụng một vòng lặp để in ra tất cả các số nguyên tố còn lại trong mảng.

Đoạn mã trên sẽ in ra tất cả các số nguyên tố từ 2 đến 100, bao gồm các số: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97.

Nếu bạn muốn tìm tất cả các số nguyên tố trong một khoảng giá trị khác, bạn có thể thay đổi giá trị của biến start và end trong đoạn mã trên tương ứng với khoảng giá trị của bạn.