Nhập vào số n,kiểm tra số n có phải số nguyên tố không ( dùng cách tối ưu nhất có thể nhé),code c++
2 câu trả lời
#include <iostream>
#include <vector>
using namespace std;
const int lim = 1e6;
int n;
vector<int> p(lim + 1, 1);
void sieve() {
p[0] = p[1] = 0;
for(int i = 2; i * i <= lim; ++i) {
if(p[i]) {
for(int j = i * i; j <= lim; j += i) p[j] = 0;
}
}
}
int main() {
sieve();
cin >> n;
cout << (p[n] ? "YES" : "NO");
}
*Đây là cách tối ưu nhất mình nghĩ ra (tìm ước (chạy tới $\sqrt{n}$))
#include <bits/stdc++.h>
using namespace std;
long long n;
int main()
{
cin >> n;
bool kt=true;
for (long long i=2; i<=sqrt(n); i++)
if (n%i==0)
{
kt=false;
break;
}
if (kt==true)
cout << n << " la so nguyen to";
else
cout << n << " khong la so nguyen to";
}
Câu hỏi trong lớp
Xem thêm
