Đăng nhập để hỏi chi tiết
- Tin Học
- Lớp 8
- 30 điểm
- nguyenductrungtphcm -
Định đề Bertran: “ Với mọi số nguyên n ≥ 2 bao giờ cũng tìm thấy số nguyên tố p thỏa mãn n < p < 2n”. Định đề này do nhà toán học Pháp Jojeph Bertran đưa ra năm 1845 sau khi đã kiểm tra với mọi n ≤ 3 000 000. Điều này đã được Tchebưsep chứng minh năm 1850. Năm 1932 Erdoeus đã tìm được cách chứng minh mới đơn giản hơn. Nhiệm vụ của bạn rộng hơn một chút: với n cho trước, hãy xác định số lượng số nguyên tố p thỏa mãn điều kiện n < p < 2n. INPUT gồm nhiều tests, mỗi test cho trên một dòng chứa số nguyên dương n (1 ≤ n ≤ 107). OUTPUT kết quả mỗi test đưa ra trên một dòng dưới dạng một số nguyên. Code theo C++
Hãy luôn nhớ cảm ơn và vote 5*
nếu câu trả lời hữu ích nhé!
TRẢ LỜI
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll nmax = 1e7 + 5;
using namespace std;
bool f[nmax + 1];
void sangnt() {
memset(f, true, sizeof(f));
f[0] = false;
f[1] = false;
for (int i = 2; i * i <= nmax; ++i) {
if (f[i] == true) {
for (int j = i * i; j <= nmax; j += i) {
f[j] = false;
}
}
}
}
ll dp[nmax + 1];
void dpnt() {
dp[0] = 0;
for (ll i = 1; i <= nmax; i++) {
dp[i] = dp[i - 1] + f[i];
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
sangnt();
dpnt();
ll n;
while (cin >> n) {
ll m = n * 2;
cout << dp[m] - dp[n] << '\n';
}
}Hãy giúp mọi người biết câu trả lời này thế nào?
51 vote
#include <bits/stdc++.h> using namespace std;
const int MAXN=3000000+5;
int n;
bool prime[MAXN*2];
void khoitao()
{
memset(prime,true,sizeof(prime));
for(int i=2;i*i<2*MAXN;i++) if (prime[i])
for(int j=2;i*j<2*MAXN;j++)
prime[i*j]=false;
return;
}
int main()
{
freopen("BERTRAN.INP","r",stdin);
freopen("BERTRAN.OUT","w",stdout);
khoitao();
while (cin>>n) {
int ans=0;
for(int i=n+1;i<2*n;i++) ans+=(int)prime[i];
cout<<ans<<'\n';
}
return 0;
}
Hãy giúp mọi người biết câu trả lời này thế nào?
3.52 vote
Bạn muốn hỏi điều gì?
Đặt câu hỏiTham Gia Group Dành Cho Lớp 8 Chia Sẻ, Trao Đổi Tài Liệu Miễn Phí
Bảng tin
Bạn muốn hỏi điều gì?
Đặt câu hỏi
Cơ quan chủ quản: Công ty Cổ phần Công nghệ Giáo dục Thành Phát
Tải ứng dụng
Inbox: m.me/hoidap247online
Trụ sở: Tầng 7, Tòa Intracom, số 82 Dịch Vọng Hậu, Cầu Giấy, Hà Nội.
Giấy phép thiết lập mạng xã hội trên mạng số 331/GP-BTTTT do Bộ Thông tin và Truyền thông.
2707
41698
2042
#include <bits/stdc++.h> #define ll long long using namespace std; const ll nmax = 1e7 + 5; using namespace std; bool f[nmax + 1]; void sangnt() { memset(f, true, sizeof(f)); f[0] = false; f[1] = false; for (int i = 2; i * i <= nmax; ++i) { if (f[i] == true) { for (int j = i * i; j <= nmax; j += i) { f[j] = false; } } } } ll dp[nmax + 1]; void dpnt() { dp[0] = 0; for (ll i = 1; i <= nmax; i++) { dp[i] = dp[i - 1] + f[i]; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); sangnt(); dpnt(); ll n; while (cin >> n) { ll m = n * 2; cout << dp[m - 1] - dp[n] << '\n'; } } Rút gọn#include <bits/stdc++.h> #define ll long long using namespace std; const ll nmax = 1e7 + 5; using namespace std; bool f[nmax + 1]; void sangnt() { memset(f, true, sizeof(f)); f[0] = false; f[1] = false; for (int i = 2; i * i <= nmax; +... xem thêm
2707
41698
2042
E thử lại nhé
312
860
284
AC rồi a :3
312
860
284
cảm ơn a khôi ❤️
2707
41698
2042
Hình như lúc đấy a k để ý phần cho nhiều test case với giới hạn đề
312
860
284
:))))), đúng như cái ava của a :))))))
2707
41698
2042
Ừ đúng ấy e, bài học kinh nghiệm đầu đời a đấy :v
312
860
284
:>