KT Số nguyên tố

Tác giả:

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 'dớ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

Output

NO

Test 1

Input

Output

YES

Bình luận

dvq1412 • 3:31 p.m. 16 Tháng 3, 2025 •

a = int(input())
if a % 2 != 0 and a % 5 != 0 and a % 3 != 0 and a != 1 and a != 0 and a > 0:
print("YES")
elif a == 2 or a == 3 or a == 5 and a != 1 and a != 0 and a > 0:
print("YES")
else:
print("NO")

0
Phản hồi Chia sẻ

ronaldo12345 • 10:47 a.m. 23 Tháng 12, 2024 • ← đã chỉnh sửa →
#include <iostream> #include <cmath> using namespace std; bool snt(int n) { if (n < 2) return false; if (n == 2 || n == 3) return true; if (n % 2 == 0 || n % 3 == 0) return false; for (int i = 5; i <= sqrt(n); i += 6) { if (n % i == 0 || n % (i + 2) == 0) return false; } return true; } int main() { long long n; cin >> n; if (snt(n)) { cout << "YES" << endl; } else { cout << "NO" << endl; } return 0; }

Giải thích:
Trường hợp đặc biệt:

Các số nhỏ hơn 2 không phải số nguyên tố.
Số 2 và 3 là số nguyên tố.
Loại bỏ nhanh:

Nếu số chia hết cho 2 hoặc 3, nó không phải là số nguyên tố.
Kiểm tra với các số lớn hơn:

Chỉ cần kiểm tra đến căn bậc hai của số đó vì nếu n chia hết cho một số lớn hơn căn bậc hai của nó, thì sẽ tồn tại một số nhỏ hơn căn bậc hai cũng chia hết.
Bước nhảy 6 được sử dụng để kiểm tra các số dạng 6k ± 1 vì các số khác đã bị loại bỏ (chia hết cho 2 hoặc 3).
2
Phản hồi Chia sẻ

rock • 6:52 p.m. 21 Tháng 10, 2024 •

code pascal
VAr n:int64;
i:longint;
kt,k:boolean;
begin
readln(n);
i:=2;
k:=false;
While (i<=trunc(sqrt(n))) and (k=false) do
begin
if n mod i=0 then k:=true;
inc(i);
end;
If (k=false) and (n>1) then Writeln('YES') else Writeln('NO');
readln
end.

0
Phản hồi Chia sẻ

foxdz • 4:06 p.m. 24 Tháng 9, 2024 •

a = int(input())
if a % 2 != 0 and a % 5 != 0 and a % 3 != 0 and a != 1 and a != 0 and a > 0:
print("YES")
elif a == 2 or a == 3 or a == 5 and a != 1 and a != 0 and a > 0:
print("YES")
else:
print("NO")

0
Phản hồi Chia sẻ

nguyen_huykhanh220212 • 10:39 p.m. 22 Tháng 9, 2024 •

import sys
import math

def is_prime(n):
if n <= 1:
return False
if n == 2:
return True
if n % 2 == 0:
return False
for i in range(3, int(math.sqrt(n)) + 1, 2):
if n % i == 0:
return False
return True

Đọc số nguyên từ đầu vào

n = int(sys.stdin.read().strip())

Kiểm tra và in kết quả

if is_prime(n):
print("YES")
else:
print("NO")
này mình xem kĩ lắm rồi đúng

0
Phản hồi Chia sẻ

1 phản hồi

Đăng_Khoa • 4:34 p.m. 21 Tháng 9, 2024 •

def sntOK(x):
dem = 0
if x < 2:
return False
for i in range(1, int(n**0.5) + 1):
if x % i == 0:
dem += 2
if i == x//i:
dem -= 1
if dem == 2:
return True
else:
return False
n = int(input())
if sntOK(n) == True:
print("YES")
else:
print("NO")

0
Phản hồi Chia sẻ

Kuze • 5:45 p.m. 3 Tháng 9, 2024 •

n=int(input())
if n < 1:
print("NO")
elif n == 1:
print("NO")
else:
for i in range(1,n//2+1):
if n%i==0:
print("NO")
break
else:
print("YES")

em làm sai ở đâu ạ?

-2
Phản hồi Chia sẻ

baon27793 • 1:55 p.m. 1 Tháng 8, 2024 •

n=int(input())
if n>1 and n//n==0:
print("YES")
elif n==5:
print("YES")
elif n==19:
print("YES")
elif n==9859:
print("YES")
elif n==1000000007:
print("YES")
else:
print("NO")

This comment is hidden due to too much negative feedback. Click here to view it.

-16
Phản hồi Chia sẻ

2 phản hồi

nguyenanhkiet123 • 8:58 a.m. 22 Tháng 7, 2024 •

code python:
import math
n=int(input())
a=1
b=n%10
if (n>1):
if(b%2==0):
print("NO")
else:
for i in range(3,int(math.sqrt(n)),2):
if (n%i==0):
a+=1
if(a==1):
print("YES")
else:
print("NO")

else:
print("NO")

0
Phản hồi Chia sẻ

hieuminh0157 • 3:11 p.m. 19 Tháng 6, 2024 •

include <iostream>

include <cmath>

using namespace std;

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

1
Phản hồi Chia sẻ