KT Số nguyên tố

Xem PDF
Tác giả:
Small
Dạng bài
Điểm: 900 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

Trong ngày thực tập đầu tiên, thầy Hải có một câu đố nho nhỏ cho các học sinh của mình. Cho một số nguyên \(n\), hãy kiểm tra \(n\) có phải là số nguyên tố hay không?

Số nguyên tố là số tự nhiên lớn hơn 1 chỉ có hai ước số dương phân biệt là 1 và chính nó.

Input:

  • Gồm một dòng duy nhất là số nguyên \(n (|n| \le 10^{12})\)

Output:

  • In ra YES nếu \(n\) là số nguyên tố. Ngược lại in ra NO.

Example

Test 1

Input 
9
Output 
NO

Test 1

Input 
7
Output 
YES

Bình luận


  • 0
    hjhjhjhjhj    9:02 a.m. 8 Tháng 4, 2024

    include <bits/stdc++.h>

    define ll long long

    const int N=1e7+2;
    using namespace std;
    ll n,a[N];
    bool snt(ll n)
    {
    if(n<2)return false;
    if(n<4)return true;
    if(n%2==0||n%3==0)return false;
    for(ll i=5;i<=sqrt(n);i+=6)
    {
    if(n%i==0||n%(i+2)==0)return false;
    }
    return true;
    }
    int main()
    {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    // freopen(".inp","r",stdin);
    // freopen(".out","w",stdout);
    cin >> n;
    if(snt(n))cout << "YES\n";
    else cout << "NO\n";
    return 0;
    }
    code này cx ok nè


    • 2
      ndt04122010    9:16 a.m. 3 Tháng 4, 2024

      include <bits/stdc++.h>

      using namespace std;
      long long snt(long long n){
      if(n<2) return 0;
      for(int i=2;i<=sqrt(n);i++)
      if(n%i==0) return 0;
      return 1;
      }
      long long n;
      int main()
      { cin>>n;
      if(snt(n)==1) cout<<"YES";
      else cout<<"NO";
      return 0;
      }


      • 0
        peter    10:33 p.m. 20 Tháng 2, 2024

        from math import sqrt
        n=int(input())
        kt=True
        for i in range (2,int(sqrt(n))+1):
        if (n%i==0):
        kt=False
        break
        if (kt==True):
        print("YES")
        else:
        print("NO")


        • -4
          tk22NguyenMinhPhuc    7:30 p.m. 22 Tháng 8, 2023

          dễ ẹc


          • 3
            DuongNhanAC    6:25 p.m. 25 Tháng 4, 2023

            Bài này Testcases có yếu quá không vậy ạ?
            Em thấy số lớn đa số trong Test đều là số chẵn


            • -17
              tk21nhilethixuan    4:24 p.m. 7 Tháng 4, 2022

              Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

              2 phản hồi

              • -5
                Toilaaibanbietko7A4    11:12 a.m. 2 Tháng 3, 2022 ← chỉnh sửa 3

                Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.


                • 15
                  dang7rickroll    8:30 p.m. 8 Tháng 9, 2021

                  \(\color{Blue}{\text{Instruction}}\)

                  PHƯƠNG PHÁP 1:

                  • Định nghĩa: Số nguyên tố là số nguyên dương chỉ có hai ước là \(1\) và chính nó.
                  • Vậy ta sẽ đếm các ước của \(N\), nếu số lượng ước của \(N = 2\), thì in ra \(Yes\), còn không thì in ra \(NO\).

                  \(\color{darkgrey}{\text{Reference TLE Code - C++}}\)

                  C++
                  #include<bits/stdc++.h>
using namespace std;

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long n,d=0;
  cin >> n;
  for (int i = 1; i<=n;i++)
  {
    if (n%i==0) dem++;
  }
  if (dem==2) cout << "YES";
  else cout << "NO";

  return 0;
}

                  • Tuy nhiên cách trên sẽ bị lỗi \(\color{darkgrey}{\text{Runtime Error}}\) (do giới hạn của \(N\)) lên tới \(1000000000000\).

                  - Vì vậy ta sẽ "rút gọn" cách làm như sau:

                  PHƯƠNG PHÁP 2:

                  • Ta nhận thấy số \(N\) không phải là số nguyên tố nếu trong khoảng từ \(1\) đến \(sqrt(n)\) có một số nguyên dương là ước của \(N\).
                  • Vì vậy phương pháp \(2\) này ta chỉ cần chạy \(for\) từ \(1\) đến \(sqrt(n)\), nếu số \(N\) chia hết cho bất kỳ \(1\) số nào trong khoảng cách, thì ngay lập tức in ra \(NO\), thoát khỏi chương trình. Còn không thì in ra \(YES\).
                  • Ta có thể viết phần chính của chương trình thành một hàm để gọn gàng hơn.
                  • Ngoài ra, số âm và số \(1\) đều không phải là số nguyên tố nên khi gặp các số này thì lập tức in ra \(NO\) ngay.

                  \(\color{green}{\text{Reference Accepted Code - C}}\)

                  C++
                  #include<stdio.h>
#include<math.h>
int ktprime (long long x)
{
    if(x==1) return 0;
    if(x<0) return 0;
    for (long long i=2;i<=sqrt(x);i++)
    {
        if(x%i==0) return 0;
    }
    return 1;

}
int main()
{
    long long n;
    scanf("%lld",&n);
    if(ktprime(n)==1) printf("YES");
    if(ktprime(n)==0) printf("NO");
    return 0;
}
                  3 phản hồi

                  • -38
                    ngoquanhao2009    10:18 a.m. 6 Tháng 7, 2021

                    Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

                    1 phản hồi