Số nguyên tố

Xem PDF



Thời gian:
Python 3 4.0s

Tác giả:
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

  • UserZero 10:08 a.m. 2 Tháng 3, 2025

    Không sàn ae nhá.
    Test lên tận 7*10^8 lận.

    Cứ kiểm tra từng số là được.

    • phamgiakhanh686868 4:00 p.m. 12 Tháng 1, 2025

      import math
      n=int(input())
      s=input()
      l=[]
      ds1=[]
      ds2=[]
      l=list(map(int,s.split()))
      for i in range(n):
      a = l[i]
      j=2
      while j<=math.sqrt(a) and a % j !=0:
      j+=1
      if a % j !=0:
      ds1.append(a)
      ds2.append(i+1)
      ln=max(ds1)
      print(max(ds1))
      while ln in ds1:
      vitri_ln_trong_ds_1=ds1.index(ln)
      print(ds2[vitri_ln_trong_ds_1],end=" ")
      ds1[vitri_ln_trong_ds_1]=0

      • SBD_01_Lam 9:14 a.m. 26 Tháng 11, 2024 chỉnh sửa 5

        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*

        • HoangTrieu_2012 8:35 p.m. 20 Tháng 11, 2024
          lm bài này cx nhanh lắm:)))
          cỡ..........
          ......1 tiếng:)))
          code Python cho ai bí nek

          import math
          def is_prime(ff):
          if ff <= 1:
          return False
          if ff == 2:
          return True
          if ff % 2 == 0:
          return False
          for i in range(3, int(math.sqrt(ff)) + 1, 2):
          if ff % i == 0:
          return False
          return True
          n = int(input())
          rbl = list(map(int, input().split()))
          gg= -1
          t = []
          for i in range(n):
          if is_prime(rbl[i]):
          if rbl[i] > gg:
          gg = rbl[i]
          t = [i + 1]
          elif rbl[i] == gg:
          t.append(i + 1)
          print(gg)
          print(*t)

          • dackhoatvd2015 5:26 p.m. 14 Tháng 10, 2024

            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;
            }

            • vuhaidang 4:46 p.m. 21 Tháng 9, 2024

              bài này 1000đ nhiều quá

              • lucky_vn0000 6:24 p.m. 5 Tháng 9, 2024

                This comment is hidden due to too much negative feedback. Click here to view it.

                • zatarainbow 4:06 p.m. 17 Tháng 8, 2024

                  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;
                  }
                  //https://top1zata.blogspot.com

                  • PY2NNguyenHuuPhucKhang 8:38 p.m. 17 Tháng 5, 2024

                    This comment is hidden due to too much negative feedback. Click here to view it.

                    • hjhjhjhjhj 8:48 a.m. 8 Tháng 4, 2024

                      include <bits/stdc++.h>

                      define ll long long

                      using namespace std;
                      bool check(ll n)
                      {
                      if (n < 2)
                      return false;
                      for (ll i = 2; i * i <= n; i++)
                      {
                      if (n % i == 0)
                      return false;
                      }
                      return true;
                      }

                      int main()
                      {
                      long long n,a[100005],maxn=-100000000005;
                      cin>>n;
                      for(int i=1;i<=n;i++) cin>>a[i];
                      for(int i=1;i<=n;i++)
                      {
                      if(check(a[i])) maxn=max(maxn,a[i]);
                      }
                      cout<<maxn<<endl;
                      for(int i=1;i<=n;i++) if(a[i]==maxn) cout<<i<<" ";
                      }

                      • 6 bình luận nữa