Hướng dẫn giải của [TS10 Kon Tum 2025 - 2026] Số nguyên tố lớn nhất
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Ý tưởng
Duyệt xâu từ trái sang phải, khi gặp chữ số thì ghép liên tiếp thành một giá trị nguyên. Nếu giá trị này lớn hơn đáp án hiện tại thì kiểm tra nguyên tố và cập nhật. Các số có tối đa ~9~ chữ số nên có thể kiểm tra nguyên tố bằng cách thử ước đến ~\sqrt x~.
Độ phức tạp
~O(|S|+q\sqrt V)~, trong đó ~q~ là số lượng số cần kiểm tra và ~V \le 10^9~.
Bình luận