Số nguyên tố
Xem PDF
Điểm:
1000 (p)
Thời gian:
2.0s
Bộ nhớ:
1023M
Input:
bàn phím
Output:
màn hình
Cho dãy số nguyên (\(a_1, a_2, ..., a_n\)), \(1 \le n \le 10000\); với mọi \(i\) sao cho \(a_i \le 10^8\).
Yêu cầu:
- Hãy tìm số nguyên tố lớn nhất trong dãy trên.
Input
- Dòng thứ nhất chứa số nguyên dương \(n\).
- Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, ..., a_n\).
Output
- Dòng thứ nhất ghi số nguyên tố lớn nhất.
- Dòng thứ hai ghi các chỉ số trong dãy mà giá trị của nó là số nguyên tố lớn nhất.
Example
Test 1
Input
9
19 7 81 33 17 4 19 21 13Output
19
1 7
Bình luận
include <bits/stdc++.h>
using namespace std;
long long n,a[10009],i,ma=0,vt=0;
bool kt(long long n)
{
if((n==2)||(n==3)) return true;
if((n%2==0)||(n%3==0)||(n<2)) return false;
int i=5,c=sqrt(n);
for(i;i<=c;i+=6)
if((n%i==0)||(n%(i+2)==0)) return false;
return true;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
cin>>n;
for(i=1;i<=n;i++)
{cin>>a[i];if(a[i]>ma&&kt(a[i])==true) {ma=a[i];vt=i;}}
cout<<ma<<'\n';
for(vt;vt<=n;vt++)
if(a[vt]==ma) cout<<vt<<" ";
return 0;
}
12 bình luận nữa