Processing math: 84%
Solutions of Sieve of Eratosthenes - MarisaOJ: Marisa Online Judge

Solutions of Sieve of Eratosthenes

Select solution language

Write solution here.


User Avatar giavinh650    Created at    2 likes

# Nhắc nhở: ### Khuyến khích mọi người nên tự tìm hiểu, suy nghĩ lời giải trước khi tham khảo ### Nên đọc kỹ hướng dẫn trước khi tham khảo bài làm ___________________________________________________________________________________ ### Cách 1: Duyệt Với mỗi số từ 1 đến n, ta kiểm tra số đó có phải là số nguyên tố hay không. Nếu số đó là số nguyên tố thì ta in ra màn hình. > Chúng ta có thể kiểm tra số nguyên tố tương tự bài [số nguyên tố 2](https://marisaoj.com/problem/25) để tăng tốc độ kiểm tra. Độ phức tạp tối ưu là O(nk=1k) ### Cách 2: Sàng nguyên tố **Các bạn có thể tham khảo hướng dẫn tại các trang này** [Sàng nguyên tố (VNOI)](https://wiki.vnoi.info/algo/algebra/prime_sieve.md) [Sieve of Eratosthenes (Wikipedia)](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) > Sau khi chúng ta hoàn thiện sàng nguyên tố thì chúng ta chỉ cần duyệt từ 2 đến n, rồi in ra những số chưa được đánh dấu. Độ phức tạp: O(N * log(log(n))) ## Bài giải: > Giải thuật: sàng nguyên tố > Độ phức tạp: O(N * log(log(n))) #clude<bitsstdc++.h>#defelonglong#defeendl\nusingnamespacestd;constN=2e6+10;f[N]={};voieve(n)/hà