KT Số nguyên tố
Xem PDF
Đ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
YESnếu \(n\) là số nguyên tố. Ngược lại in raNO.
Example
Test 1
Input
9Output
NOTest 1
Input
7Output
YES
Bình luận
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).
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.
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")
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")
này mình xem kĩ lắm rồi đúng
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")
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 ạ?
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
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")
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";
}
include <iostream>
include <cmath>
bool isPrime(long long n) {
if (n <= 1) return false;
if (n <= 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
for (long long i = 5; i * i <= n; i += 6) {
if (n % i == 0 || n % (i + 2) == 0)
return false;
}
return true;
}
int main() {
long long n;
std::cin >> n;
std::cout << (isPrime(n) ? "YES" : "NO");
return 0;
}
12 bình luận nữa