Đưa ra ước nguyên tố nhỏ nhất của các số từ 1 đến N

[La_Van_Kien (La Văn Kiên)]

Xin thỉnh giáo hướng giải của bài này với dữ liệu đầu vào như trên…
#daynhauhoc

[SITUVN.gcd]

Bài này tương đương phân tích thừa số nguyên tố.
Bạn biết phân tích thừa số nguyên tố của 1 số không? Bài này chỉ lấy thừa số nguyên tố nhỏ nhất cho nhiều số. Số 1 là trường hợp đặc biệt.

[tntxtnt]

100 cái N=10^9 thì in ra gì nổi

[hungaya (Hung)]

Sàng Eratosthenes thôi.
Bước khởi tạo mảng arr[1…N] gán 0 toàn bộ.
Bước đánh dấu, thay vì true/false, thì đánh theo số nguyên tố.

for (int x = 2; x*x <= N; x++)
  if (arr[x] == 0) {
    arr[x] = x;
    for (int y = x*x; y <= N; y += x)
      if (arr[y] == 0)
        arr[y] = x;
  }

for (int x = 3; x <= N; x += 2)
  if (arr[x] == 0)
    arr[x] = x;

Mấy cái linh tinh tự thêm nha.

[rogp10]

Dùng sàng phân đoạn thì được, vì thực ra sàng chạy nhanh nhất khi có kích thước tầm vài MB (phải benchmark). Bạn có thể khai báo bitset qua vector