PrimeQ
Details and Options
- PrimeQ is typically used to test whether an integer is a prime number.
- A prime number is a positive integer that has no divisors other than 1 and itself.
- PrimeQ[n] returns False unless n is manifestly a prime number.
- For negative integer n, PrimeQ[n] is effectively equivalent to PrimeQ[-n].
- With the setting GaussianIntegers->True, PrimeQ determines whether a number is a Gaussian prime.
- PrimeQ[m+In] automatically works over Gaussian integers.
Examples
open all close allBasic Examples (2)
Scope (4)
Options (1)
Applications (22)
Basic Applications (5)
Multicolumn[If[PrimeQ[#], Style[#, Red, Bold], #]& /@ Range[100], 10, ...]
Prime[5]Generate random prime numbers:
RandomPrime[1000, 10]AllTrue[%, PrimeQ]The distribution of Gaussian primes:
ArrayPlot[Boole[Table[PrimeQ[a + b I, GaussianIntegers -> True],
{a, 100}, {b, 100}]]]Find the first few prime powers that are not prime:
Select[Range[100], PrimePowerQ[#] && !PrimeQ[#]&]Special Sequences (11)
g = Flatten[Table[a + I b, {a, -40, 40}, {b, -40, 40}]];
p = Select[g, PrimeQ[#, GaussianIntegers -> True]&];ComplexListPlot[p, PlotRange -> All, PlotMarkers -> {{●, 1}}, Axes -> False, AspectRatio -> 1]Eisenstein integers are complex numbers of the form 
where a and b are integers and ω is the cube root of unity 
:
ω = Exp[2π I / 3];e = Select[Flatten[Table[a + b ω, {a, -30, 30}, {b, -30, 30}], 1], Abs[#] < 20&];Check wether an Eisenstein integer is prime:
primeQ[a_] := Or[PrimeQ[AlgebraicNumberNorm[a]], (PrimeQ[Abs[a]] && Mod[Abs[a], 3] == 2)]primeQ[ω]primeQ[5]primes = Select[e, primeQ];ComplexListPlot[primes, PlotRange -> All, PlotMarkers -> Automatic, Axes -> False, AspectRatio -> 1] The quadratic polynomial 
is prime for 
:
PrimeQ[Table[x ^ 2 + x + 41, {x, 0, 39}]]Recognize Fermat primes, prime numbers of the form 
:
PrimeQ[2 ^ 2 ^ 3 + 1]The number 
is not a Fermat prime:
PrimeQ[2 ^ 2 ^ 7 + 1]Recognize Carmichael numbers, composite numbers n that satisfy 
mod 
for all integers b that are relatively prime to n:
cnumberQ[n_] := !PrimeQ[n] && Mod[n, CarmichaelLambda[n]] == 1;The number 1729 is a Carmichael number; 1310 is not:
cnumberQ[1729]cnumberQ[1310]Recognize Wieferich primes, prime numbers p such that 
divides 
:
wprimeQ[n_] := PrimeQ[n] && (Mod[2 ^ (n - 1) - 1, n ^ 2] == 0);wprimeQ[1093]There are only two known Wieferich primes:
Select[Range[10 ^ 4], wprimeQ]Recognize Gaussian Mersenne primes, prime numbers n such that 
is a Gaussian prime:
gaussianMersennePrimeQ[n_] := PrimeQ[(1 + I) ^ n - 1, GaussianIntegers -> True];Select[Range[1000], gaussianMersennePrimeQ]Let 
be all numbers of the form 
:
hilbertQ[n_] := Divisible[n - 1, 4];
h = Select[Range[1000], hilbertQ];Check that the product of two numbers is still in 
:
{a, b} = RandomChoice[h, 2];
hilbertQ[a b]Recognize Hilbert primes, prime numbers that have no divisors in 
other than 1 and itself:
hprimeQ[n_] := If[Length[Select[h, Divisible[n, #] && hilbertQ[n] && hilbertQ[#]&]] == 2, True, False];Find the first 10 Hilbert primes:
Select[h, hprimeQ, 10]Test whether or not the first 47 Mersenne prime exponents are prime:
AllTrue[PrimeQ[MersennePrimeExponent[Range[47]]], #&]Cases[Range[1000], n_ /; PrimeQ[n] && (NextPrime[n] == n + 2) :> {n, n + 2}]Find Mersenne prime exponents:
FindInstance[(2 ^ q - 1) == p && 0 < q < p < 100, {q, p}, Primes]MersennePrimeExponentQ[5]Number Theory (6)
Find numbers that are prime over Gaussian integers and integers:
Select[Prime[Range[20]], PrimeQ[#, GaussianIntegers -> True]&]They are congruent to 3 mod 4:
Mod[%, 4]These numbers cannot be written as the sum of two squares:
SquaresR[2, %%]Find numbers that are composite over Gaussian integers but prime over integers:
Select[Range[100], CompositeQ[#, GaussianIntegers -> True] &&
PrimeQ[#] &]All of them except for 2 are congruent to 1 mod 4:
Mod[Drop[%, 1], 4]These numbers can be written as the sum of two squares in 8 ways:
SquaresR[2, Drop[%%, 1]]Plot the difference between two consecutive primes:
ListLinePlot[Table[Prime[n + 1] - Prime[n], {n, 1, 100}]]The infinite sum of reciprocals of prime powers that are not prime converges:
Total[1. / Select[Range[10 ^ 5], PrimePowerQ[#] && !PrimeQ[#]&]]The distribution of primes over integers:
data = Select[Range[100], PrimeQ];𝒟 = EmpiricalDistribution[data];DiscretePlot[Evaluate[CDF[𝒟, x]], {x, 1, 100}, ExtentSize -> Right]The distribution of Gaussian primes over Gaussian integers:
data = {Re[#], Im[#]}& /@ Select[Flatten[Table[a + b I, {a, 500}, {b, 500}]], PrimeQ];𝒟 = EmpiricalDistribution[data];DiscretePlot3D[Evaluate[CDF[𝒟, {x, y}]], {x, 1, 5}, {y, 1, 5}, ExtentSize -> Right]Properties & Relations (22)
Primes represents the domain of all prime numbers:
Element[2 ^ 107 - 1, Primes]Prime gives 
prime number:
Table[Prime[n], {n, 10}]PrimeQ[%]RandomPrime generates random prime numbers:
RandomPrime[100, 10]PrimeQ[%]PrimePowerQ gives True for all prime numbers:
PrimeQ[37]PrimePowerQ[37]Primes that are congruent to 1 mod 4 are not prime powers in the Gaussian integers:
PrimeQ[29]Mod[29, 4]PrimePowerQ[29, GaussianIntegers -> True]Prime powers are divisible by exactly one prime number:
PrimePowerQ[625]Select[Divisors[625], PrimeQ]The only divisors of a prime number p is 1 and p:
PrimeQ[17]Divisors[17]The only even prime number is 2:
PrimeQ[2]PrimeQ gives False for all composite numbers:
CompositeQ[12]PrimeQ[12]CompositeQ gives False for all primes:
PrimeQ[23]CompositeQ[23]Every integer greater than 1 either is a prime number itself or can be represented as the product of prime numbers:
PrimeQ[17]FactorInteger[17]PrimeQ[24]FactorInteger[24]The GCD of two prime numbers is 1; consequently, two prime numbers are relatively prime:
PrimeQ[{7, 11}]GCD[7, 11]CoprimeQ[7, 11]The LCM for prime numbers is their product:
PrimeQ[{5, 7, 2}]LCM[5, 7, 2] == 5 7 2The sum of the prime divisors of a prime number returns the original number:
PrimeQ[19]DivisorSum[19, #&, PrimeQ]Prime numbers of the form 
, where the exponent p is also prime, are called Mersenne primes:
MersennePrimeExponent[4]PrimeQ[2 ^ % - 1]MersennePrimeExponents are prime numbers:
PrimeQ[Table[MersennePrimeExponent[n], {n, 10}]]Use FactorInteger to find all prime divisors of a number:
Part[FactorInteger[2434500], All, 1]Select[Divisors[2434500], PrimeQ]PrimeOmega returns 1 for prime numbers:
PrimeOmega[29]PrimeQ[29]PrimePi gives the number of primes:
PrimePi[1000]The number of prime numbers up to 1000:
Count[Table[PrimeQ[n], {n, 1, 1000}], True]PrimeNu counts the number of prime divisors of a number:
PrimeNu[65]Select[Divisors[65], PrimeQ]Simplify expressions containing prime numbers:
Simplify[Mod[a ^ p, p] == Mod[a, p], a∈Integers && p∈Primes]Solve over Primes:
Solve[(p - 1) < p ^ 2 + p + 1 < 100, p, Primes]Interactive Examples (1)
Neat Examples (3)
Visualize when 
is divisible by primes. Each row of dots corresponds to the divisors of 
, which are labeled along the horizontal axis:
NumberLinePlot[Table[Select[Range[Prime[n]], (Divisible[Prime[n] - 1, #] && # > 1 && PrimeQ[#])&], {n, 1, 40}], PlotRange -> All]Plot the prime numbers that are the sum of three squares:
ArrayMesh[Boole[Table[PrimeQ[a ^ 2 + b ^ 2 + c ^ 2], {a, 10}, {b, 10}, {c, 10}]]]Plot the Ulam spiral of prime numbers:
ulam[n_] := Partition[Permute[Range[n ^ 2], Accumulate[Take[Flatten[{{n ^ 2 + 1} / 2, Table
[(-1) ^ j i, {j, n}, {i, {-1, n}}, {j}]}], n ^ 2]]], n];ArrayPlot[ulam[101] Boole[PrimeQ[ulam[101]]], ColorFunction -> "Rainbow", ColorRules -> {0 -> White}]
MathWorld
An Elementary Introduction to the Wolfram Language
An Elementary Introduction to the Wolfram Language
An Elementary Introduction to the Wolfram Language
NKS|OnlineText
Wolfram Research (1988), PrimeQ, Wolfram Language function, https://reference.wolfram.com/language/ref/PrimeQ.html (updated 2003).
CMS
Wolfram Language. 1988. "PrimeQ." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2003. https://reference.wolfram.com/language/ref/PrimeQ.html.
APA
Wolfram Language. (1988). PrimeQ. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/PrimeQ.html