Đăng nhập để hỏi chi tiết
Số nguyên tố là số chỉ có hai ước là 1 và chính nó. Viết chương trình tìm số nguyên tố lớn nhất trong dãy. Dữ liệu vào: Tệp văn bản Nguyento.inp gồm hai dòng: - Dòng 1: Số nguyên dương n (1 n 106) - Dòng 2: Gồm n số nguyên dương (mỗi số cách nhau một kí tự trống, đều 106). Dữ liệu ra: Tệp văn bản Nguyento.out chứa duy nhất số nguyên tố lớn nhất, nếu không có số nào thỏa mãn thì ghi -1; 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 <iostream>
#include <algorithm>
#define N 1000005
using namespace std;
bool is_prime[N];
void sieve() {
fill(is_prime, is_prime+N, true);
is_prime[0] = false; is_prime[1] = false;
for (int i=2; i*i<=N; ++i) {
for (int j=i*i; j<=N; j+=i)
is_prime[j] = false;
}
}
int main() {
//freopen("Nguyento.inp", "r", stdin);
//freopen("Nguyento.out", "w", stdout);
sieve();
int res = -1;
int n ; cin >> n;
for (int i=1; i<=n; ++i) {
int v ; cin >> v;
if (is_prime[v]) res = max(res, v);
}
cout << res;
}
$\\$
`\bb\color{green}{\text{@Daoanhviet96}}`
Hãy giúp mọi người biết câu trả lời này thế nào?
52 vote
- ThaiHuyy
Mod Hoidap247
#include <bits/stdc++.h>
using namespace std;
bool kt(long long n)
{
if (n<2)
return false;
for (int i=2;i*i<=n;i++)
if (n%i==0)
return false;
return true;
}
int main()
{
long long n,max;
cin>>n;
long long a[n+1];
for(int i=0;i<n;i++) cin>>a[i];
int i=0;
for (i=0;i<n;i++)
if (kt(a[i]))
{
max=a[i];
break;
}
for (int j=i+1;j<n;j++)
if(kt(a[j]) and(a[j]>max))
max=a[j];
if (max==0) cout<<-1;
else
cout<<max;
}
Hãy giúp mọi người biết câu trả lời này thế nào?
51 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.
0
327
0
#include<bits/stdc++.h> using namespace std; bool kt(long long n) { long long dem=0; for(long long i=1; i*i<=n; i++) { if(n%i==0) dem+=2; if(i*i==n) dem--; } if(dem==2) return true; return false; } int main() { freopen("Nguyento.INP","r",stdin); freopen("Nguyento.OUT","w",stdout); long long n,max,i; cin>>n; long long a[n]; for(long long i=1; i<=n; i++) cin>>a[i]; max=2; for(long long i=1; i<=n; i++) if(kt(a[i])) if(a[i]>max) max=a[i]; cout<<max; else cout<<"-1"; } Rút gọn#include<bits/stdc++.h> using namespace std; bool kt(long long n) { long long dem=0; for(long long i=1; i*i<=n; i++) { if(n%i==0) dem+=2; if(i*i==n) dem--; } if(dem==2) return true; return false; } int main() { ... xem thêm
0
327
0
viết lại rùi sửa giúp mik với
0
327
0
viết theo code của mik ý
2901
47938
1864
Đây nha bạn, nhưng theo mình thì code này nếu test mạnh thì không ăn hết test đâu. #include<iostream> using namespace std; bool kt(long long n) { long long dem=0; for(long long i=1; i*i<=n; i++) { if(n%i==0) dem+=2; if(i*i==n) dem--; } if(dem==2) return true; return false; } int main() { freopen("Nguyento.INP","r",stdin); freopen("Nguyento.OUT","w",stdout); long long n,max,i; cin>>n; long long a[n]; for(long long i=1; i<=n; i++) cin>>a[i]; max = -1; for(long long i=1; i<=n; i++) if(kt(a[i])) if(a[i]>max) max=a[i]; cout << max; } Rút gọnĐây nha bạn, nhưng theo mình thì code này nếu test mạnh thì không ăn hết test đâu. #include<iostream> using namespace std; bool kt(long long n) { long long dem=0; for(long long i=1; i*i<=n; i++) { if(n%i==0) dem+=2; if(i*i==... xem thêm
0
327
0
- Có 50% test với 1≤ n ≤ 103. - Có 50% test với 103< n ≤ 106. nó đó
2901
47938
1864
Code của bạn là `O(n\sqrt{k})` (k là phần tử của mảng), nếu n và giá trị trong mảng mà quá lớn thì code của bạn không qua nổi. Code của mình là `O(NloglogN)`, do mình lấy N=10^6 làm giá trị cố định nên có thể AC được.