BCPRIME PTIT spoj – Kiểm tra số nguyên tố

Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCPRIME/

1. Đề bài Kiểm tra số nguyên tố

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.

Dữ liệu

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

Kết quả

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

Ví dụ

2. Code check số nguyên tố

Các bạn có thể dùng nhanh hàm này:

bool snt(int x)
{
    if (x<2) 
        return 0;
    for (int i=2; i<=sqrt(x); i++) 
        if (x%i==0) 
            return 0;
    return 1;
}

a. code pascal

var
        N,i:longint;

begin
        readln(n);
        if n<2 then
                begin
                        writeln('NO');
                        exit;
                end;
        for i:=2 to trunc(sqrt(n)) do
                if n mod i = 0 then
                        begin
                                writeln('NO');
                                exit;
                        end;
        writeln('YES');
end.

#include <stdio.h>
#include <math.h>
using namespace std;

bool snt(int x)
{
    if (x<2) 
        return 0;
    for (int i=2; i<=sqrt(x); i++) 
        if (x%i==0) 
            return 0;
    return 1;
}

int main()
{
    int n; scanf("%d",&n);
    printf(snt(n) ? "YES" : "NO");
    return 0;
}

c. Code C++ viết trên chương trình chính

#include <stdio.h>
#include <math.h>
using namespace std;
int main()
{
    int n;
    //freopen("BCPRIME.inp","r",stdin);
    scanf("%d",&n);
    if (n<2)
    {
        printf("NO");
        return 0;
    }
    int i;
    int m=sqrt(n);
    for (i=2; i<=m; i++)
        if (n%i==0)
        {
            printf("NO");
            return 0;
        }
    printf("YES");
    return 0;
}