Bài này thì bạn tìm số lớn nhất trong mảng (gọi là n), rồi tìm số nguyên tố (snt) nhỏ nhất lớn hơn n. Bạn chỉ cần kiểm tra lần lượt các số lẻ lớn hơn n có phải là snt hay không. Đặt i = n + 2 nếu n lẻ và i = n + 1 nếu n chẵn, xét i rồi tăng cứ tăng i 2 bước mà xét tiếp.
Vì khoảng các giữa 2 số nguyên tố kề nhau là rất nhỏ so với chúng, nên số các số i cần xét đến khi ra đáp án không nhiều. Ví dụ khoảng cách giữa 2 snt 31397 và 31469 chỉ là 72 thôi. Nếu n là 31398 thì số các số i cần xét là (31469-31399+1)/2 = 36.
Còn để xét i có phải là snt hay không, bạn xét thử i có chia hết cho các số lẻ từ 3 đến sqrt(i) không thôi. Bởi vì nếu i chia hết cho 1 số nào đó sau sqrt(i) thì sẽ cho ra số nằm trong đoạn 3 đến sqrt(i). Nếu bạn muốn nhanh hơn nữa thì có thể tìm hiểu thêm các cách tối ưu, giảm các số mà i cần phải chia thử. Còn muốn nặng đô hơn nữa (nhanh nhất có thể) ^^ thì dùng thuật toán Miller-Rabin để xét i có phải là snt.
http://en.wikipedia.org/wiki/Primality_test