02/10/2018, 13:56
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ữ ...
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ụ
| INPUT | OUTPUT |
| 2 | YES |
| INPUT | OUTPUT |
| 4 | NO |
Bài này không có gì đặc biệt. cứ áp dụng thuật toán kiểm tra số nguyên tố là được.
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;
}
1 2 3 4 5 6 7 8 9 | 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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | 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. |
b. Code C++ Kiểu dùng hàm
#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;
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | #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;
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | #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; } |
