Bác nào chỉ cho em về cái thuật toán kiểm tra số nguyên tố với

Bác nào chỉ cho em về cái thuật toán kiểm tra số nguyên tố với

Bác nào chỉ cho em về cái thuật toán kiểm tra 1 số n có phải là số nguyên tố ko với (với n lớn trên 100 chữ số) Em tìm ra thuật toán rùi nhưng đọc chả hiểu gì cả. Bác nào vào giảng hộ em phát. Nếu làm hộ em cái đoạn chương trình trên C++ thì tốt nhất
http://vi.wikipedia.org/wiki/Ki%E1%BB%83m_tra_Miller-Rabin

Đọc cũng "hàn lâm" thật
Ngày xưa toàn kiểm tra trong giới hạn Interger của Pascal thôi. Cứ While ... do 1 phát là ra

Có giải thuật rồi mà, bác chỉ việc ốp code vào thôi. Còn muốn hiểu nó thì không đơn giản đâu, vì người ta xây dựng lên cái concepts cũng không đơn giản. Bác tham khảo qua quyển Introduction to Algorithms - MIT hay Four primality testing algorithms đi, có nói đến Miller-Rabin test đấy.
http://www.mat.uniroma2.it/~schoof/millerrabinpom.pdf

Em vẫn ko ốp được nên mới hỏi, làm thử theo cách này thì đa phần đều đúng nhưng vẫn có nhiều trường hợp sai lè lè. VD khi n=25 nó vẫn báo là nguyên tố. Đây là bài ốp thử với số nhỏ, khi chạy với 25 nó báo là nguyên tố mới đau
#include <iostream.h>
#include <conio.h>
#include <stdlib.h>;
long n;
int main()
{
long s,m,i,k,a,b;
cout <<"n= ";
cin >> n;
if (n%2==0) {cout<<"hopso";
return 0;
}
s=0;m=n-1;
while (m%2==0)
{s++;
m=m/2;
}
randomize();
for (int j=1;j<=1000;j++)
{
a=random(n-3)+2;
b=1;
for (i=1;i<=m;i++)
b=(b*a)%n;
if(b==1) {cout<<"nguyen to";
return 0;
}
for (k=0;k<=s-1;k++)
{
if (b==n-1) {cout<<"nguyen to";
return 0;
}
b=(b*b)%n;
}
}
cout <<"hop so";
return 0;
}

bàc chì? cĂ?n kiĂ?m tra tư? 1 'Ắn trĂ?n cù?a n /2 là? 'ù? thò?a màfn rĂ?i
(nẮu em nhớ ko nhĂ?m)

tớ nhớ không nhầm thì kiểm tra điến sqrt(n) là đủ ...để kiếm lại quả code Pascal đã

Muốn biết x có là số nguyên tố không,
kiểm tra xem x có chia hết cho các số từ 2 đến sqrt(x) không?
Nếu x không chia hết cho bất kì số nào từ 2-->sqrt(x) thì x là số nguyên tố:
bool SNT(const int x)
{
for (int i=2; i<=sqrt(x); i++)
if ( x % i ==0) return false;
return true;
}

Cà? 3 bàc nòi bĂn trĂn 'Ă?u 'ùng, nhưng chì? phù? hợp với sẮ nhò?, và? già?i thuẶt như vẶy khĂng tẮi ưu.
@htcuong: toi mai em cùfng là?m thư?, thẮy cài nà?y hay hay

Híc, bài này em làm với số lớn n cỡ khoảng 100 chữ số trở lên. For trâu bò từ 2 đến sqrt(n) thì ko có biết có xong trước tết ko nữa

Số hàng trăm chữ số mà mấy bác cứ tư vấn kiểm tra bằng cách thông thường
Kiểm tra Miller-Rabin chỉ là thuật toán xác suất thôi (kiểm tra 1 số là nguyên tố với xác suất ~1).
Muốn lập trình cụ thể bằng C++ thì phải định nghĩa cách biểu diễn số lớn hàng trăm chữ số (bằng một chuỗi các byte/word.... chẳng hạn). Cái này ngày xưa em cũng làm rồi nhưng bây giờ ko biết còn nhớ ko Nếu có thể thì mai em làm giúp bác