Đề bài: Cho số nguyên N (1 <= N <= 2 * 10^6) nhập từ bàn phím. Hãy đưa ra số M là số nguyên tố gần với N nhất. Số nguyên tố gần với N được định nghĩa là một số nguyên tố mà khoảng cách từ N tới nó là nhỏ nhất. Nếu ta tìm được 2 số nguyên tố có cùng khoảng cách tới N, ưu tiên in ra màn hình số nhỏ hơn (codelearn.io - practice easy).
Testcase #1:
Input:
51
Output:
53
Testcase #2:
Input:
1000
Output:
997
Solution: Dựng sàng Eratosthenes, sau đó tìm số nguyên tố gần nhất bên trái và bên phải. Nếu khoảng cách đến số nguyên tố bên trái lớn hơn khoảng cách đến số bên phải thì in số bên phải ra, còn lại in số bên trái.
Code:
No comments:
Post a Comment