Tạo số nguyên tố
Xem dạng PDF
Gửi bài giải
Điểm:
5,00
Giới hạn thời gian:
2.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C++
Cho số nguyên dương n.
Người ta muốn biến n thành một số nguyên tố bằng phép biến đổi như sau:
- Sau mỗi phép biến đổi, gán giá trị cho n bằng tổng của tất cả các ước của chính nó, ngoại trừ 1 và n.
- Phép biến đổi kết thúc khi n trở thành một số nguyên tố.
Hãy tìm và in ra số nguyên tố được tạo thành từ n bằng cách sử dụng phép biến đổi trên. Nếu không thể tạo ra số nguyên tố từ số ban đầu, hãy trả về -1.
Ví dụ:
- Với n = 12 đầu ra sẽ là makePrime(12) = 5
Phép biến đổi thứ 1: n = 2 + 3 + 4 + 6 = 15
Phép biến đổi thứ 2: n = 3 + 5 = 8
Phép biến đổi thứ 3: n = 2 + 4 = 6
Phép biến đổi thứ 4: n = 2 + 3 = 5
Do 5 là số nguyên tố nên phép biến đổi kết thúc tại đây.
Bình luận