Tổng snt từ 1->n 1<=n<=1e8 Ngôn ngữ Java/C, giải thích thuật toán

Chào các em học sinh lớp 10, thầy rất vui khi thấy các em bắt đầu quan tâm đến các bài toán tối ưu hóa thuật toán. Với giới hạn n lên tới 100 triệu (1e8), chúng ta không thể sử dụng phương pháp kiểm tra số nguyên tố thông thường (duyệt từng số) vì sẽ gây ra hiện tượng quá thời gian (Time Limit Exceeded).

Để giải quyết bài toán này, phương pháp tối ưu nhất chính là Sàng nguyên tố Eratosthenes. Dưới đây là hướng dẫn chi tiết:

1. Giải thích thuật toán Sàng Eratosthenes:

• Ý tưởng: Thay vì kiểm tra từng số, chúng ta sẽ tạo một mảng đánh dấu (boolean) có kích thước n+1. Ban đầu, giả định tất cả các số từ 2 đến n đều là số nguyên tố.
• Bước 1: Bắt đầu từ số 2, nếu số đó chưa bị đánh dấu, đó chính là số nguyên tố.
• Bước 2: Loại bỏ tất cả các bội số của số nguyên tố vừa tìm được bằng cách đánh dấu chúng là “không phải số nguyên tố” (bắt đầu từ bình phương của số đó để tối ưu).
• Bước 3: Lặp lại cho đến khi xét hết căn bậc hai của n.
• Kết quả: Sau khi sàng, ta chỉ cần cộng dồn các giá trị còn lại trong mảng là số nguyên tố.

2. Cài đặt bằng ngôn ngữ C:

Trong C, chúng ta dùng mảng kiểu char hoặc bool để tiết kiệm bộ nhớ cho 100 triệu phần tử.

include <stdio.h>
include <vector>

// Sử dụng mảng toàn cục hoặc cấp phát động để tránh tràn bộ nhớ stack
char is_prime[100000001];

int main() {
    int n = 100000000;
    for (int i = 2; i <= n; i++) is_prime[i] = 1;
    
    for (int p = 2; p * p <= n; p++) {
        if (is_prime[p]) {
            for (int i = p * p; i <= n; i += p)
                is_prime[i] = 0;
        }
    }
    
    long long sum = 0;
    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) sum += i;
    }
    printf("Tong la: %lld", sum);
    return 0;
}

3. Cài đặt bằng ngôn ngữ Java:

Trong Java, lưu ý rằng mảng boolean tiêu tốn 1 byte mỗi phần tử, nên 100 triệu phần tử sẽ tốn khoảng 100MB RAM, nằm trong giới hạn cho phép thông thường của các trình chấm bài.

public class Main {
    public static void main(String[] args) {
        int n = 100000000;
        boolean[] isPrime = new boolean[n + 1];
        java.util.Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;

        for (int p = 2; p * p <= n; p++) {
            if (isPrime[p]) {
                for (int i = p * p; i <= n; i += p)
                    isPrime[i] = false;
            }
        }

        long sum = 0;
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) sum += i;
        }
        System.out.println("Tong la: " + sum);
    }
}

Lưu ý quan trọng cho các em:

• Kiểu dữ liệu: Tổng của các số nguyên tố đến 100 triệu sẽ vượt quá khả năng lưu trữ của kiểu số nguyên 32-bit (int). Các em bắt buộc phải dùng kiểu long (trong Java) hoặc long long (trong C) để chứa biến tổng.
• Bộ nhớ: Với n = 1e8, mảng boolean/char chiếm khoảng 100MB. Nếu đề bài yêu cầu giới hạn bộ nhớ chặt chẽ hơn (ví dụ 64MB), các em cần nghiên cứu thêm về Sàng bit (Bitset) để tiết kiệm bộ nhớ hơn nữa.

Chúc các em học tập tốt và nắm vững thuật toán quan trọng này!