MERSENNE - Nguyên tố Mersenne
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Số nguyên tố Mersenne là số nguyên có dạng 2n − 1 với n là một số nguyên nào đó .
Yêu cầu: Tính số lượng số nguyên tố Mersenne trong đoạn [a;b] với a,b là hai số nguyên dương.
Input
Gồm một dòng duy nhất chứa hai số nguyên dương a và b (~ 1 ≤ a, b ≤ 2^{31} − 1 ~).
Output
Gồm một dòng duy nhất chứa một số nguyên là số lượng số nguyên tố Mersenne trong đoạn [a;b].
Sample
Input #1
1 2
Output #1
0
Input #2
1 3
Output #2
1
Problem source: Free Contest 55
Bình luận
Đề bài phải là 2^n - 1 nhé các bạn.
Thêm nữa số nguyên tố Mersenne là số có dạng 2^n - 1 (với n là số nguyên tố và bản thân nó cũng là số nguyên tố)
Ví dụ n = 5 => số Mersenne là 31: vì 2^5 - 1 = 31 (5 là số nguyên tố và 31 cũng là số nguyên tố)
n = 4 không thể tạo ra số Mersenne vì: 2^4 - 1 = 15 (4 không phải số nguyên tố và 15 cũng vậy)