Đề bài: Nhập vào 1 số nguyên dương n. Kiểm tra số đó có phải là số nguyên tố hay không?
Hiên nay có rất nhiều các cách (thuật toán) để giải quyết bài toán này. Nhưng mình xin đưa ra 1 cách nhanh nhất giúp giảm thời gian xuất kết quả. Đây là thuật toán của các sinh viên cntt Ấn Độ nghĩ ra. Và đã được tặng giải Nobe Tin Học - Một giải thưởng lớn của giới Tin học nói chung, và công nghệ thông tin nói riêng.
Dưới đây là đoạn code tham khảo:
#include<iostream.h>
#include<math.h>
int snt(int n)
{
int k=sqrt(n);
if(n<2) return 0;
for(int i =2;i<=k;i++)
if(n%i==0) return 0;
return 1;
}
void lietkesonguyento(int n)//ham liet ke cac so nguyen to nho hon n
{
for(int i =0;i<=n;i++)
{
if(snt(i))
cout<<i<<" ";
}
}
int main()
{
int n;
cout<<"Moi nhap n= ";
cin>>n;
if(snt(n)==1)
cout<<"La so nguyen to!";
else
cout<<"Ko la so nguyen to!";
}
Kết quả của chương trình:
Theo Đinh Quang Trưởng
