0.Số nguyên tố


Submit solution

Points: 1 (partial)
Time limit: 1.0s
Memory limit: 98M

Author:
Problem types

enter image description here


Một số được gọi là số nguyên tố nếu nó chỉ có 2 ước là 1 và chính nó. Số 0 và 1 không được coi là số nguyên tố.

Yêu cầu: Cho số n, hãy kiểm tra xem n có là số nguyên tố hay không.

Input

Một dòng duy nhất chứa số n (0<=n<=4*10^9)

Output

In ra “YES” nếu n là số nguyên tố, và “NO” trong trường hợp còn lại.


Comments


  • 0
    manh_ĐTVT5_K60  commented on Sept. 18, 2021, 1:58 a.m.

    include<iostream>

    include<math.h>

    using namespace std; int main() { long x,dem=0; cin>>x; if(x<=2||x%2==0) { cout<<"NO"; return 0; }

    for(long i=3;i<sqrt(x);i+=2) { if(x%i==0)
    { cout<<"NO"; return 0; } } cout<<"YES";

    return 0; }


  • 0
    ga123  commented on Sept. 15, 2021, 2:27 a.m.

    sau khi suy nghĩ về tối ưu thì mình đã nâng cấp thuật toán để giảm thời gian còn 1 nửa và giảm số bước xuống tối thiểu trong trường hợp xấu nhất

    
    #include"stdio.h"
    #include"stdlib.h"
    int main()
    {
    long long n;int i;
    scanf("%ld",&n);
    if(n==2) 
    {
    printf("YES");exit(0);
    }
    if(n==1)
    {
        printf("NO");exit(0);
    }
    if(n<0||n%2==0) 
    {
    printf("NO");
    exit(0);
    }
    for(i=3;i*i<=n;i+=2)
    if(n%i==0)
    {
        printf("NO");
        exit(0);
    }
    printf("YES");
    }

  • 0
    ga123  commented on Sept. 5, 2021, 8:21 a.m. edited

    sau khi lắng nghe ý kiến comment thì mình đã sửa lại code như sau, để khử tình huống của số bình phương:

    #include"bits/stdc++.h"
    using namespace std;
    int main()
    {
    cout<<setprecision(10)<<fixed;
    long a,i,c=1;
    cin>>a;
    if(a==0||a==1)
    cout<<"NO";
    else 
    {
    for(i=2;i*i<=a;i++)
    {
        if(a%i==0)
        {
            cout<<"NO";
            c--;
            break;
        }
    }
    if(c!=0) cout<<"YES";
    }
    
    };

  • 0
    ga123  commented on Sept. 5, 2021, 3:07 a.m. edit 2

    bai nay rut ngan duoc hon nx.

    #include"bits/stdc++.h"
    using namespace std;
    int main()
    {
    cout<<setprecision(10)<<fixed;
    long a,i,c=1;
    cin>>a;
    if(a==0||a==1)
    cout<<"NO";
    else 
    {
    for(i=2;i*i<a;i++)
    {
        if(a%i==0)
        {
            cout<<"NO";
            c=0;
            break;
        }
    }
    if(c!=0) cout<<"YES";
    }
    
    };

    • 0
      TICHPX  commented on Sept. 5, 2021, 4:31 a.m.

      Code này số 49 là số nguyên tố đấy em


      • 0
        ga123  commented on Sept. 5, 2021, 8:18 a.m.

        vâng ạ, code của em cứ dinh số có giá trị bằng bình phương số nguyên tố là bị hỏng ạ. 4, 9, 25, đều bị thành số nguyên tố ạ. bộ test này không mấy bộ số nguyên tố bình phương nên chạy code ra đúng hết ạ :3


  • -1
    vietcong666  commented on Sept. 4, 2021, 9:51 a.m.

    :((

    include<bits/stdc++.h>

    using namespace std;

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


  • -2
    trung0710  commented on Aug. 16, 2020, 2:16 a.m.

    package Bai2;

    import java.util.Scanner;

    public class Person { public static void main(String[] args) { int n; Scanner sc = new Scanner(System.in); System.out.println("Nhap n :"); n = sc.nextInt(); int dem = 0; for (int i = 1; i <= n; i++) { if (n % i == 0) { dem++; } } if (dem == 2) System.out.println(n + " la so nguyen to"); else System.out.println(n + " k la so nguyen to"); sc.close(); } }