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


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

    • 1
      tranthanh05012011    2:38 p.m. 1 Tháng 8, 2023

      1 upvote cho @dang7rickroll:))


      • 5
        VoBaThongL921    12:29 p.m. 17 Tháng 10, 2021

        Nice. Hồi tui mới học hoang mang mấy bài này ghê, toàn bị tle. Chỉ mong có người viết hint cho thôi:) nên chắc mấy bạn học sau cũng vậy


        • -21
          minhkhoidepzai    3:47 p.m. 18 Tháng 9, 2021

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


          • 7
            dang7rickroll    4:00 p.m. 18 Tháng 9, 2021

            mình viết cái này để dành cho những ai chưa hiểu và chưa biết, còn bạn hiểu và biết rồi thì vui lòng lướt qua ạ


            • -30
              messilionel    3:48 p.m. 18 Tháng 9, 2021

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


              • 12
                dang7rickroll    4:01 p.m. 18 Tháng 9, 2021

                bạn biết làm rồi thì bạn lướt qua, nó có ảnh hưởng gì tới bạn không?


                • 2
                  hongquanyl1    3:35 p.m. 6 Tháng 2, 2022

                  lmao lmao :))


                  • -36
                    messilionel    11:03 a.m. 26 Tháng 9, 2021

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


                    • -35
                      messilionel    11:03 a.m. 26 Tháng 9, 2021

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

                9 bình luận nữa