In ra các số nguyên tố từ 1 đến n (sàng số nguyên tố)
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
In ra các số nguyên tố từ 1 đến n sử dụng sàng số nguyên tố
Ràng buộc: n đến 10^6
Input 01:
Copy
10
Output 01:
Copy
2 3 5 7
Input 02:
Copy
100
Output 02:
Copy
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
Bình luận
nhớ dùng sàng số nguyên tố bằng cách này nè dễ hiểu
Ý tưởng của sàng Eratosthenes:
Tạo một mảng isPrime[] có kích thước n + 1, gán tất cả các giá trị là true, ngoại trừ isPrime[0] và isPrime[1] là false.
Với mỗi số i từ 2 đến sqrt(n):
Nếu i là số nguyên tố (tức isPrime[i] == true), đánh dấu tất cả bội số của i (từ i*i đến n) là false.
In ra tất cả các i từ 2 đến n mà isPrime[i] == true.