Số nguyên tố

Xem PDF

Tất cả bài nộp

Các bài nộp tốt nhất

Thời gian:

Python 3 4.0s

Tác giả:

Small

Dạng bài

Đ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 13

Output

19
1 7

Bình luận

Hướng dẫn c++

spoiler warning

build hàm kiểm tra số nguyên tố
Kiểm tra số nguyên tố ngay sau khi nhập a[i]
dùng vector<> để lưu lại các vị trí của số nguyên tố lớn nhất
Nếu a[i] > m thì clear() mảng vector, cập nhật giá trị m và nhập vào vector
Nếu a[i] == m thì nhập vào vector

code cho ai bất lực lắm rồi=))

C++

#include <bits/stdc++.h>
#define fi first
#define se second
const int N =2e5+4;
typedef long long ll;
using namespace std;
ll n,m=-1,k,a;
bool check(ll n){
    if (n<2) return 0;
    if (n<4) return 1;
    if (n%2==0||n%3==0) return 0;
    for (ll i=5;i*i<=n;i++) if (n%i==0||n%(i+2)==0) return false;
    return true;
}
signed main() {
    vector <ll> v;
    scanf ("%lld",&n);
    for (ll i=1;i<=n;i++){
        scanf ("%lld",&k);
        if (check(k)==true){
            if (k>m){
                v.clear();
                m=k;
                v.emplace_back(i);
            }
            else if (k==m) {
                v.emplace_back(i);
            }
        }
    }
    printf ("%lld\n",m);
    for (auto it:v){
        printf ("%lld ",it);
    }
    return 0;
}

yêu cầu admin Small giảm thời gian xuống 1s*

-2

Phản hồi

14 bình luận nữa