Số học 2 - Số nguyên tố, Sàng Eratosthenes

Sàng Eratosthenes (Sieve of Eratosthenes)

Sàng Eratosthenes dùng để tìm các số nguyên tố nhỏ hơn hoặc bằng số nguyên N$N$ nào đó. Nó còn có thể được sử dụng để kiểm tra một số nguyên nhỏ hơn hoặc bằng N$N$ hay không.

Nguyên lí hoạt động của sàng là vào mỗi lần duyệt, ta chọn một số nguyên tố và loại ra khỏi sàng tất cả các bội của số nguyên tố đó mà lớn hơn số đó. Sau khi duyệt xong, các số còn lại trong sàng đều là số nguyên tố.

............................................

Bài tập áp dụng:

• SPOJ - PRIME1
• VNOJ - NKABD

Nguồn: https://vnoi.info/wiki/translate/he/Number-Theory-2.md?fbclid=IwAR1ZujYeB1puxbXmArS1YddjuKSpHnS-I7xSDRkbIq78KrB6vnslbsr2Gtc