Kiểm tra số nguyên tố
Xem dưới dạng PDFKiểm tra một số có phải là số nguyên tố hay không
Nhập liệu
Dòng đầu nhập vào \(t\) (\(1 \le t \le 10^5\)), là số lượng test-case.
T dòng tiếp theo mỗi dòng chứa một số \(N\) (\(1 \le N \le 10^9\))
Kết quả
Nếu \(N\) là số nguyên tố thì in 1 ngược lại in 0
Dữ liệu mẫu
2
13 -16Kết quả mẫu
1 0
Nhận xét
import math
def checkPrime(n): if(n==2 | n==3): print("1 \n") return if(n<2 or n%2==0 or n%3==0): print("0 \n") return
k = 1 while(6k-1<=math.sqrt(n)): if(n%(6k-1)==0 | n%(6*k+1)==0): print("0 \n") return k+=1 print("1 \n") return
t = int(input()) for i in range(t): n = int(input()) checkPrime(n)
Bài dễ quá ạ
include<bits/stdc++.h>
using namespace std;
bool prime(long long n){ if(n<2) return 0; if(n==2 || n==3) return 1; if(n%2==0 || n%3==0) return 0; long long k = 1; while(6k-1<=sqrt(n)){ if(n%(6k-1)==0 || n%(6*k+1)==0) return 0; k++; } return 1; }
int main(){ ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); long long t; cin >> t; while(t--){ long long n; cin >> n; cout << prime(n) << endl; } return 0; }