stanford-oval/wikipedia huggingface dataset:
Số nguyên tố
Tính chất trong giải tích > Chứng minh định lý Euclid bằng giải tích

Chứng minh của Euler về sự tồn tại vô số số nguyên tố xét tổng nghịch đảo các số nguyên tố
Euler chứng minh được rằng với một số thực  x bất kỳ, tồn tại một số nguyên tố  p sao cho tổng trên lớn hơn  x. Nếu chỉ có một số hữu hạn các số nguyên tố thì tổng này phải đạt giá trị lớn nhất tại số nguyên tố lớn nhất thay vì tăng dần qua các giá trị của  x, do đó có vô số số nguyên tố. Tốc độ gia tăng giá trị của tổng này được mô tả rõ hơn trong định lý thứ hai của Mertens. Để so sánh, tổng
không tăng đến vô hạn khi  n tiến đến vô hạn (xem bài toán Basel). Trong trường hợp này, số nguyên tố xuất hiện thường xuyên hơn so với bình phương các số tự nhiên, mặc dù cả hai tập hợp đều là vô hạn. Định lý Brun phát biểu rằng tổng nghịch đảo các số nguyên tố sinh đôi
là hữu hạn. Do định lý này nên không thể áp dụng cách của Euler để chứng minh giả thuyết số nguyên tố sinh đôi rằng có vô số cặp số nguyên tố sinh đôi.
Tính chất trong giải tích > Số lượng số nguyên tố nằm dưới một số cho trước

Bài chi tiết: Định lý số nguyên tố và Hàm đếm số nguyên tố
Hàm đếm số nguyên tố  \pi (n) được định nghĩa là số lượng số nguyên tố không lớn hơn  n. Ví dụ,  \pi (11)=5, nghĩa là có 5 số nguyên tố nhỏ hơn hoặc bằng 11. Có một số phương pháp để tính giá trị chính xác của  \pi (n) nhanh hơn so với khi liệt kê tất cả các số nguyên tố lớn đến  n, chẳng hạn như thuật toán Meissel–Lehmer. Định lý số nguyên tố phát biểu rằng  \pi (n) tiệm cận với  n/\log n hay
nghĩa là tỉ số giữa  \pi (n) và phân số ở vế phải tiến về 1 khi  n tăng đến vô hạn. Kéo theo đó, xác suất để một số nhỏ hơn  n được chọn ngẫu nhiên là số nguyên tố tỉ lệ nghịch với số chữ số của  n. Đồng thời, số nguyên tố thứ  n tỉ lệ thuận với  n\log n và độ dài trung bình của khoảng cách nguyên tố tỉ lệ thuận với  \log n. Một xấp xỉ chính xác hơn của  \pi (n) được cho bởi tích phân logarit bù
Tính chất trong giải tích > Cấp số cộng

Cấp số cộng là một dãy số hữu hạn hoặc vô hạn sao cho các số liên tiếp trong dãy đều có chênh lệch bằng nhau. Chênh lệch đó được gọi là mô đun (công sai) của cấp số cộng. Ví dụ,
là cấp số cộng vô hạn với mô đun 9. Trong một cấp số cộng, phép chia của tất cả các số cho mô đun đều cho số dư bằng nhau; trong ví dụ trên, số dư đó bằng 3. Vì cả mô đun 9 và số dư 3 đều là bội của 3 nên các phần tử khác trong dãy cũng vậy. Do đó, cấp số cộng đã cho chỉ chứa một số nguyên tố duy nhất, đó chính là số 3. Tổng quát, cấp số cộng vô hạn
có thể chứa nhiều hơn một số nguyên tố chỉ khi số dư  a và mô đun  q nguyên tố cùng nhau. Khi đó, theo định lý Dirichlet về cấp số cộng, cấp số cộng đó chứa vô số số nguyên tố.
Số nguyên tố trong cấp số cộng mô đun 9. Mỗi hàng trong thanh nhỏ nằm ngang chỉ một trong chín cấp số cộng mod 9 khác nhau, trong đó số nguyên tố được đánh dấu màu đỏ. Cấp số cộng 0, 3 hoặc 6 mod 9 chỉ chứa nhiều nhất một số nguyên tố (số 3); các cấp số cộng còn lại là 2, 4, 5, 7 và 8 mod 9 chứa vô số số nguyên tố với số lượng số nguyên tố như nhau trong mỗi cấp số cộng
Định lý Green–Tao cho thấy tồn tại các cấp số cộng hữu hạn dài tùy ý chỉ chứa các số nguyên tố.
Tính chất trong giải tích > Giá trị nguyên tố của đa thức bậc hai

Euler nhận thấy rằng hàm
cho giá trị là số nguyên tố với  1\leq n\leq 40, mặc dù các giá trị hợp số bắt đầu xuất hiện khi  n lớn hơn 40. Việc tìm ra giải thích cho hiện tượng này chính là tiền đề của lý thuyết số đại số với số Heegner và bài toán lớp số. Giả thuyết F của Hardy–Littlewood dự đoán mật độ số nguyên tố trong các giá trị của đa thức bậc hai với hệ số nguyên về mặt tích phân logarit và hệ số của đa thức. Không có đa thức bậc hai nào được chứng minh là chỉ cho các giá trị nguyên tố.
Xoắn Ulam sắp xếp các số tự nhiên thành một mặt phẳng hai chiều, xoắn ở các hình vuông đồng tâm quanh điểm gốc với số nguyên tố được đánh dấu. Dễ thấy trong ví dụ này, các số nguyên tố chỉ tập trung ở một số đường chéo nhất định, ngụ ý rằng có một số đa thức bậc hai cho giá trị nguyên tố thường xuyên hơn các đa thức khác.
Tính chất trong giải tích > Hàm zeta và giả thuyết Riemann

Bài chi tiết: Giả thuyết Riemann
Giả thuyết Riemann (1859) là một trong những bài toán chưa được giải nổi tiếng nhất toán học và một là trong bảy bài toán thiên niên kỷ, yêu cầu tìm các nghiệm số của hàm zeta Riemann  \zeta (s). Hàm này là một hàm giải tích trên tập số phức. Với số phức  s có phần thực lớn hơn 1, nó bằng một tổng vô hạn trên tất cả số nguyên và một tích vô hạn trên tất cả số nguyên tố:
Sự bằng nhau này giữa một tổng và một tích (do Euler tìm ra) được gọi là tích Euler. Tích Euler có thể được suy ra từ định lý cơ bản của số học và cho thấy sự liên hệ giữa hàm zeta và số nguyên tố. Nó dẫn đến một cách chứng minh khác về sự tồn tại vô số số nguyên tố: nếu chỉ có một số hữu hạn số nguyên tố thì dấu bằng giữa tổng và tích cũng xảy ra tại  s=1 nhưng tổng có tính phân kỳ (đó chính là chuỗi điều hòa  1+{\tfrac {1}{2}}+{\tfrac {1}{3}}+\dots ) trong khi tích có tính hội tụ (mang giá trị hữu hạn), mâu thuẫn.
Giả thuyết Riemann phát biểu rằng nghiệm số của hàm zeta là tất cả các số âm chẵn hoặc các số phức với phần thực bằng 1/2. Chứng minh ban đầu của định lý số nguyên tố được dựa trên dạng không chặt chẽ của giả thuyết này cho rằng không có nghiệm số nào có phần thực bằng 1, mặc dù còn có thêm một số cách chứng minh cơ bản khác. Hàm đếm số nguyên tố có thể được biểu diễn bởi công thức tường minh của Riemann thành một tổng mà trong đó, mỗi số hạng đến từ một nghiệm số của hàm zeta: số hạng chính của tổng là tích phân logarit và các số hạng còn lại làm cho giá trị của tổng dao động quanh số hạng chính đó. Trong trường hợp này, các nghiệm số làm ảnh hưởng đến sự phân phối các số nguyên tố. Nếu giả thuyết Riemann là đúng, độ dao động đó sẽ nhỏ lại và sự phân phối tiệm cận các số nguyên tố được cho bởi định lý số nguyên tố cũng đúng trên các khoảng nhỏ hơn rất nhiều (có độ dài gần bằng căn bậc hai của  x đối với khoảng nằm gần một số  x).
Đại số trừu tượng > Số học mô đun và trường hữu hạn

Bài chi tiết: Số học mô đun
Số học mô đun là một dạng khác của số học thông thường chỉ dùng các số  \{0,1,2,\dots ,n-1\} với một số tự nhiên  n được gọi là mô đun. Bất kỳ số tự nhiên nào khác đều có thể được ánh xạ vào hệ thống này bằng cách thay nó bằng số dư của nó khi được chia bởi  n. Mô đun tổng, hiệu và tích được tính bằng cách thực hiện phép thế bằng số dư trong phép chia của tổng, hiệu hoặc tích các số nguyên thông thường. Sự bằng nhau giữa các số nguyên có liên quan đến khái niệm đồng dư trong số học mô đun:  x và  y đồng dư (ký hiệu  x\equiv y{\bmod {n}}) khi phép chia của chúng bởi  n cho số dư bằng nhau. Tuy nhiên, trong hệ thống số đó, chỉ có thể xảy ra phép chia cho một số khác 0 khi và chỉ khi mô đun là số nguyên tố. Chẳng hạn, với mô đun 7, có thể tồn tại phép chia cho 3:  2/3\equiv 3{\bmod {7}}, vì khi nhân cả hai vế cho 3 thì ta được biểu thức đúng  2\equiv 9{\bmod {7}}. Nhưng với mô đun 6 (là một hợp số), không thể tồn tại phép chia cho 3: phương trình  2/3\equiv x{\bmod {6}} vô nghiệm vì khi nhân cả hai vế cho 3 thì vế trái trở thành số 2 còn vế phải trở thành số 0 hoặc số 3. Trong đại số trừu tượng, khả năng thực hiện phép chia có nghĩa rằng mô đun một số nguyên tố tạo thành một trường được gọi là trường hữu hạn, trong khi các mô đun khác chỉ tạo ra vành.
Bằng số học mô đun, có thể suy ra được một số định lý về số nguyên tố. Ví dụ, định lý nhỏ Fermat phát biểu rằng nếu  a\not \equiv 0 (mod  p) thì  a^{p-1}\equiv 1 (mod  p). Lấy tổng trên tất cả giá trị của  a, ta được phương trình
đúng khi  p là số nguyên tố. Giả thuyết Giuga cho rằng phương trình này là điều kiện đủ để  p là số nguyên tố. Theo định lý Wilson, một số nguyên  p>1 là số nguyên tố khi và chỉ khi giai thừa  (p-1)! đồng dư với –1 mod  p. Với một hợp số \;n=r\cdot s\;thì định lý này không đúng, vì khi đó có một trong hai thừa số chia hết cả n và  (n-1)! nên không thể có  (n-1)!\equiv -1{\pmod {n}}.
Đại số trừu tượng > Số p-adic

Bài chi tiết: Số p-adic
Cấp  p-adic  \nu _{p}(n) của một số nguyên  n là số lần xuất hiện của  p trong phân tích nguyên tố của  n. Khái niệm này có thể được mở rộng cho số hữu tỉ: cấp  p-adic của một phân số  m/n được xác định là  \nu _{p}(m)-\nu _{p}(n). Khi đó, giá trị tuyệt đối  p-adic  |q|_{p} của một số hữu tỉ  q là  |q|_{p}=p^{-\nu _{p}(q)}. Khi nhân một số nguyên với giá trị tuyệt đối  p-adic của nó thì các thừa số  p trong phân tích nguyên tố của số nguyên đó bị khử và chỉ còn lại các thừa số nguyên tố khác. Giống như khi đo khoảng cách giữa hai số thực bằng giá trị tuyệt đối thông thường, khoảng cách giữa hai số hữu tỉ có thể được đo bằng độ dài  p-adic, tức là giá trị tuyệt đối  p-adic của hiệu hai số đó. Theo định nghĩa khoảng cách đó, hai số được gọi là gần nhau (có khoảng cách nhỏ) khi hiệu giữa chúng có thể chia hết bởi một lũy thừa bậc cao của  p. Bằng cùng một cách mà số thực được tạo thành từ số hữu tỉ và khoảng cách giữa chúng cùng một số giá trị giới hạn được thêm vào để hợp lại thành một trường đầy đủ, các số hữu tỉ với khoảng cách  p có thể được mở rộng sang một trường đầy đủ khác được gọi là số  p-adic.
Các khái niệm về cấp, giá trị tuyệt đối và trường đầy đủ suy ra từ chúng có thể được khái quát hóa cho trường số đại số cùng với định chuẩn (ánh xạ nhất định từ nhóm nhân của trường đó sang một nhóm cộng được sắp toàn phần), giá trị tuyệt đối (ánh xạ nhân nhất định từ một trường sang số thực), và vị trí (sự mở rộng sang trường đầy đủ mà trong đó tập cho trước là một tập trù mật) của chúng. Chẳng hạn, sự mở rộng từ tập số hữu tỉ sang tập số thực là một vị trí mà tại đó khoảng cách giữa hai số là giá trị tuyệt đối thông thường của hiệu hai số đó. Ánh xạ tương ứng sang một nhóm cộng là logarit của giá trị tuyệt đối đó, mặc dù nó không thỏa mãn tất cả yêu cầu của một định chuẩn. Theo định lý Ostrowski, trước khái niệm tự nhiên về tương đương, số thực và số  p-adic cùng cấp và giá trị tuyệt đối của chúng là định chuẩn, giá trị tuyệt đối và vị trí duy nhất trên tập số hữu tỉ. Nguyên lý Hasse cho phép giải nhiều bài toán trên số hữu tỉ bằng cách hợp các nghiệm từ các vị trí của chúng lại với nhau, một lần nữa nhấn mạnh tầm quan trọng của số nguyên tố trong lý thuyết số.
Đại số trừu tượng > Phần tử nguyên tố trong vành

Vành giao hoán là một cấu trúc đại số có định nghĩa phép cộng, phép trừ và phép nhân. Tập số nguyên là một vành và số nguyên tố trong tập đó đã được khái quát hóa sang lý thuyết vành với thuật ngữ phần tử nguyên tố và phần tử tối giản. Một phần tử  p của vành  R được gọi là phần tử nguyên tố nếu nó khác 0, không có nghịch đảo (không phải phần tử đơn vị) và thỏa mãn điều kiện: khi  p chia hết tích  xy gồm hai phần tử trong  R thì nó cũng chia hết ít nhất một trong hai phần tử  x và  y. Một phần tử được gọi là phần tử tối giản nếu nó không phải phần tử đơn vị, cũng không phải là tích của hai phần tử khác phần tử đơn vị. Trong vành số nguyên, các phần tử nguyên tố và tối giản tạo thành cùng một tập hợp
Trong một vành bất kỳ, mọi phần tử nguyên tố đều là phần tử tối giản. Phát biểu ngược lại của nó chỉ đúng trong miền phân tích nhân tử duy nhất.
Định lý cơ bản của số học là đúng (theo định nghĩa) trong miền phân tích nhân tử duy nhất. Ví dụ về một miền như thế là vành số nguyên Gauss  \mathbb {Z} [i], vành các số phức dạng  a+bi với  i là đơn vị ảo và  a và  b là số nguyên bất kỳ. Các phần tử nguyên tố của vành đó được gọi là số nguyên tố Gauss. Một số nguyên tố trong vành số nguyên có thể không phải là số nguyên tố trong vành số nguyên Gauss; chẳng hạn, số 2 có thể được viết thành tích của hai số nguyên tố Gauss  1+i và  1-i. Số nguyên tố hữu tỉ (phần tử nguyên tố trong vành số nguyên) đồng dư với 3 mod 4 là số nguyên tố Gauss, nhưng số nguyên tố hữu tỉ đồng dư với 1 mod 4 không phải vậy. Đó là một hệ quả của định lý Fermat về tổng của hai số chính phương, phát biểu rằng một số nguyên tố lẻ  p có thể được biểu diễn thành tổng của hai số chính phương,  p=x^{2}+y^{2}, và do đó có thể được phân tích thành  p=(x+iy)(x-iy), chỉ khi  p đồng dư với 1 mod 4.
Đại số trừu tượng > I-đê-an nguyên tố

Bài chi tiết: I-đê-an nguyên tố
Không phải mọi vành đều là miền phân tích nhân tử duy nhất. Chẳng hạn, trong vành các số  a+b{\sqrt {-5}} (với  a và  b là số nguyên), số 21 có hai cách phân tích:  21=3\cdot 7=(1+2{\sqrt {-5}})(1-2{\sqrt {-5}}), trong đó cả bốn thừa số đều là tối giản, nên nó không có một phân tích nhân tử duy nhất. Để mở rộng khái niệm phân tích nhân tử duy nhất sang các lớp vành khác lớn hơn, có thể thay thế thuật ngữ về số bằng thuật ngữ về i-đê-an, một tập hợp con của các phần tử trong một vành chứa tổng của mỗi cặp phần tử của nó và tích của mỗi phần tử của nó với một phần tử trong vành. I-đê-an nguyên tố, vốn khái quát hóa phần tử nguyên tố trong trường hợp i-đê-an chính tạo ra bởi một phần tử nguyên tố là một i-đê-an nguyên tố, là một công cụ quan trọng và chủ đề nghiên cứu chính trong đại số giao hoán, lý thuyết số đại số và hình học đại số. Các i-đê-an nguyên tố trong vành số nguyên là (0), (2), (3), (5), (7), (11),... Định lý cơ bản của số học được khái quát hóa thành định lý Lasker–Noether biểu diễn một i-đê-an bất kỳ trong một vành giao hoán Noether thành giao của các i-đê-an sơ cấp, một dạng khái quát hóa thích hợp của lũy thừa nguyên tố.
Phổ của một vành là một không gian hình học mà các điểm trong đó là các i-đê-an nguyên tố của vành đó. Thuật ngữ này giúp ích nhiều cho hình học đại số và nhiều khái niệm liên quan khác cũng xuất hiện trong hình học và lý thuyết số. Chẳng hạn, sự phân tích hoặc phân chia i-đê-an nguyên tố khi áp dụng trong một trường mở rộng, một bài toán cơ bản của lý thuyết số đại số, thì có tương đồng với sự phân chia trong hình học. Các khái niệm này thậm chí còn có thể hỗ trợ giải một số bài toán đặc biệt liên quan đến số nguyên trong lý thuyết số. Ví dụ, có thể dùng i-đê-an nguyên tố trong vành số nguyên của trường số bậc hai để chứng minh luật tương hỗ bậc hai, một phát biểu về sự tồn tại của biểu thức căn bậc hai mô đun một số nguyên tố nguyên. Những cố gắng ban đầu để chứng minh định lý cuối của Fermat đã dẫn đến sự ra đời khái niệm số nguyên tố chính quy, những số nguyên tố nguyên liên quan đến sự không tồn tại phân tích nhân tử duy nhất trong trường số nguyên chia đường tròn. Bài toán có bao nhiêu số nguyên tố nguyên có thể được phân tích thành một tích gồm nhiều i-đê-an nguyên tố trong một trường số đại số được giải quyết bằng định lý mật độ Chebotarev mà khi được áp dụng cho số nguyên chia đường tròn thì có trường hợp đặc biệt là định lý Dirichlet về số nguyên tố trong cấp số cộng.
Đại số trừu tượng > Lý thuyết nhóm

Trong lý thuyết nhóm hữu hạn, định lý Sylow phát biểu rằng nếu lũy thừa của một số nguyên tố  p^{n} chia hết cấp của một nhóm thì nó có một nhóm con với cấp  p^{n}. Theo định lý Lagrange, một nhóm với cấp nguyên tố là nhóm cyclic, và theo định lý Burnside thì một nhóm có cấp chia hết được bởi đúng hai số nguyên tố là nhóm giải được.
Phương pháp tính

Trong một thời gian dài, lý thuyết số nói chung và ngành nghiên cứu số nguyên tố nói riêng từng được xem là ví dụ kinh điển về toán học thuần túy khi không có ứng dụng nào ngoài phạm vi toán học, ngoại trừ việc dùng các bánh răng với số răng là số nguyên tố để hạn chế mài mòn. Thậm chí, một số nhà lý thuyết số như nhà toán học người Anh G. H. Hardy còn tự hào về chính họ khi làm những công trình nghiên cứu hoàn toàn không có ý nghĩa quân sự gì.
Góc nhìn này đã bị xóa bỏ vào những năm 1970, khi số nguyên tố đã có thể được dùng làm cơ sở để tạo ra các thuật toán mật mã hóa khóa công khai. Những ứng dụng này đã góp phần đẩy mạnh hoạt động nghiên cứu thuật toán thực hiện phép tính trên số nguyên tố và các phương pháp kiểm tra tính nguyên tố của một số. Thuật toán kiểm tra tính nguyên tố cơ bản nhất, giải thuật chia thử, quá chậm đối với số rất lớn. Một nhóm thuật toán hiện đại có thể áp dụng được cho một số bất kỳ, trong khi còn có các thuật toán hiệu quả hơn dành cho các nhóm số đặc biệt. Đa số thuật toán kiểm tra tính nguyên tố chỉ cho biết đầu vào của chúng có phải là số nguyên tố hay không. Một số đoạn chương trình khác còn xuất ra một (hoặc tất cả) thừa số nguyên tố từ đầu vào là hợp số và được gọi là thuật toán phân tích số nguyên. Số nguyên tố cũng có ứng dụng trong điện toán như giá trị tổng kiểm, bảng băm và bộ sinh số giả ngẫu nhiên.
Phương pháp tính > Giải thuật chia thử

Bài chi tiết: Chia thử
Phương pháp cơ bản nhất để kiểm tra tính nguyên tố của một số nguyên  n cho trước được gọi là chia thử. Thuật toán này chia  n cho tất cả số nguyên từ 2 đến căn bậc hai của  n. Khi có bất kỳ số nguyên nào chia hết  n thì  n là hợp số, ngược lại thì nó là số nguyên tố. Các số lớn hơn căn bậc hai đó không cần được kiểm tra, vì khi  n=a\cdot b thì một trong hai thừa số  a và  b nhỏ hơn hoặc bằng căn bậc hai của  n. Một dạng tối ưu khác là chỉ kiểm tra các thừa số nguyên tố trong khoảng đó. Chẳng hạn, để kiểm tra xem 37 có phải là số nguyên tố hay không, thuật toán này chia nó cho các số nguyên tố trong khoảng từ 2 đến √37, đó là số 2, 3 và 5. Cả ba phép chia đều có số dư khác 0 nên 37 chính là số nguyên tố.
Phương pháp này có thể được mô tả một cách đơn giản, nhưng không thực tế khi kiểm tra tính nguyên tố của các số nguyên lớn, vì số phép chia nó thực hiện tăng dần theo cấp số nhân khi số chữ số của số nguyên đó càng nhiều. Tuy nhiên, giải thuật chia thử vẫn được sử dụng để tìm nhanh hợp số với thừa số nhỏ trước khi áp dụng những phương pháp phức tạp hơn đối với các số vượt qua được giải thuật đó.
Phương pháp tính > Sàng

Bài chi tiết: Sàng Eratosthenes
Trước khi máy tính ra đời, nhiều bảng số liệt kê tất cả số nguyên tố hoặc phân tích nguyên tố đến một giới hạn cho trước đã được phát hành rộng rãi. Phương pháp cổ xưa nhất để lập danh sách số nguyên tố được gọi là sàng Eratosthenes. Hình minh họa bên phải cho thấy một dạng tối ưu của phương pháp này. Một sàng khác hiệu quả hơn để giải quyết bài toán đó là sàng Atkin. Trong toán học nâng cao, lý thuyết sàng áp dụng các phương pháp tương tự vào nhiều bài toán khác.
Phương pháp tính > Các thuật toán đặc biệt và số nguyên tố lớn nhất đã biết

Xem thêm: Danh sách số nguyên tố
Cùng với các thuật toán nói trên áp dụng được cho bất kỳ số tự nhiên nào, một vài số với dạng đặc biệt còn có thể được kiểm tra tính nguyên tố nhanh hơn. Ví dụ, kiểm tra Lucas–Lehmer có thể xác định được một số Mersenne (lũy thừa của 2 trừ 1) có phải là số nguyên tố hay không một cách tất định với thời gian bằng với một vòng lặp của kiểm tra Miller–Rabin. Đó là lý do kể từ năm 1992 (tính đến tháng 12 năm 2018) số nguyên tố lớn nhất đã biết luôn là một số nguyên tố Mersenne. Có giả thuyết cho rằng có vô số số nguyên tố Mersenne.
Bảng dưới đây liệt kê các số nguyên tố lớn nhất đã biết theo nhiều dạng khác nhau. Một vài trong số đó được tìm thấy qua điện toán phân tán. Năm 2009, dự án Great Internet Mersenne Prime Search đã được trao giải thưởng 100.000 USD cho số nguyên tố đầu tiên có ít nhất 10 triệu chữ số thập phân. Tổ chức Biên giới Điện tử cũng có giải thưởng lần lượt là 150.000 và 250.000 USD dành cho số nguyên tố có ít nhất 100 triệu và 1 tỷ chữ số.
| Dạng số nguyên tố | Số nguyên tố | Số chữ số | Thời gian | Tìm ra bởi |
| --- | --- | --- | --- | --- |
| Mersenne | 2136.279.841 − 1 | 41.024.320 | 12 tháng 10 năm 2024 | Luke Durant, Great Internet Mersenne Prime Search |
| Proth | 10.223 × 231.172.165 + 1 | 9.383.761 | 31 tháng 10 năm 2016 | Péter Szabolcs, PrimeGrid |
| Giai thừa | 422.429! − 1 | 2.193.027 | Tháng 2 năm 2022 | Ryan Propper |
| Giai thừa nguyên tố | 6.369.619# − 1 | 2.765.105 | Tháng 8 năm 2024 | Nick Merrylees, PrimeGrid |
| Sinh đôi | 2.996.863.034.895 × 21.290.000 ± 1 | 388.342 | Tháng 9 năm 2016 | Tom Greer, PrimeGrid |
Phương pháp tính > Phân tích số nguyên

Bài chi tiết: Phân tích số nguyên
Cho một hợp số  n, công việc xuất ra một (hoặc tất cả) thừa số nguyên tố được gọi là phân tích của  n. Công việc này khó hơn đáng kể so với kiểm tra tính nguyên tố, và mặc dù tồn tại nhiều thuật toán phân tích nhưng chúng đều chậm hơn so với các phương pháp nhanh nhất để kiểm tra tính nguyên tố. Giải thuật chia thử và thuật toán RHO có thể được dùng để tìm các nhân tử rất nhỏ của  n, và thuật toán phân tích bằng đường cong elliptic có thể hiệu quả khi  n có các nhân tử lớn vừa phải. Một số phương pháp phù hợp đối với số lớn bất kỳ không phụ thuộc vào độ lớn của nhân tử bao gồm sàng cấp hai và sàng trường số thông thường. Giống như kiểm tra tính nguyên tố, có một số thuật toán phân tích yêu cầu đầu vào có dạng đặc biệt, trong đó có sàng trường số đặc biệt. Tính đến tháng 2 năm 2020 số lớn nhất được phân tích bằng một thuật toán thông thường là RSA-250, một số có 250 chữ số (829 bit) và là tích của hai số nguyên tố lớn.
Thuật toán Shor cho phép phân tích bất kỳ số nguyên nào với số bước đa thức trong một máy tính lượng tử. Tuy nhiên, với công nghệ hiện nay thì thuật toán này chỉ hoạt động được với các số rất nhỏ. Tính đến tháng 10 năm 2012 số lớn nhất được phân tích bằng thuật toán Shor trong một máy tính lượng tử là 21.
Phương pháp tính > Ứng dụng khác trong điện toán

Một số thuật toán mật mã hóa khóa công khai, chẳng hạn như RSA và trao đổi khóa Diffie−Hellman được dựa trên số nguyên tố lớn (phổ biến nhất là số nguyên tố 2048 bit). RSA dựa vào giả thiết rằng thực hiện phép nhân hai số lớn  x và  y dễ hơn nhiều so với khi tính  x và  y (giả sử là hai số nguyên tố cùng nhau) nếu chỉ biết một tích  xy. Trao đổi khóa Diffie−Hellman dựa vào thực tế rằng có một số thuật toán hiệu quả đối với lũy thừa mô đun (tính  a^{b}{\bmod {c}}), trong khi phép tính ngược lại (logarit rời rạc) được cho là một bài toán khó.
Số nguyên tố được sử dụng thường xuyên trong bảng băm. Chẳng hạn phương pháp ban đầu của Carter và Wegman đối với băm phổ quát được dựa vào việc tính hàm băm bằng cách chọn ngẫu nhiên hàm tuyến tính mô đun số nguyên tố lớn. Carter và Wegman đã khái quát hóa phương pháp này cho băm  k-độc lập bằng cách sử dụng đa thức bậc cao mô đun số nguyên tố lớn. Cũng như trong hàm băm, số nguyên tố được dùng trong kích thước của bảng băm dựa trên dò cấp hai để đảm bảo rằng chuỗi dò bao phủ hết bảng đó.
Một số phương pháp giá trị tổng kiểm được dựa trên kiến thức toán học về số nguyên tố. Chẳng hạn giá trị tổng kiểm dùng trong ISBN được xác định bằng cách lấy tổng của tất cả các chữ số (ngoài chữ số cuối cùng) mô đun 11. Vì 11 là số nguyên tố nên phương pháp này có thể phát hiện các chữ số bị sai và chuyển vị của các chữ số liền kề nhau. Adler-32, một công cụ kiểm tra tổng kiểm khác, sử dụng số học mô đun 65521, số nguyên tố lớn nhất nhỏ hơn  2^{16}. Số nguyên tố cũng được dùng trong bộ sinh số giả ngẫu nhiên, trong đó có bộ sinh số đồng dư tuyến tính và Mersenne Twister.