IsPrime

Tests whether n is a prime number.

✓ checked against that system · ! checked, with disagreements (hover a chip)WikipediaPrimality test↗Prime number↗MathWorldPrimalityTest↗PrimeNumber↗WikidataQ49008↗Encyclopedia of MathematicsPrime_number↗nLabprime number↗Britannicatopic/prime-number↗OEISA000040↗Wolfram LanguagePrimeQ!↗Rosetta CodePrimality by trial division↗

IsPrime(n)tests whether $n$ is prime.

SageMathis_prime(n)✓↗SymPyisprime(n)↗Oscaris_prime(ZZ(n))Juliais_prime(ZZ(n))Rustis_prime(n)

IsPrime(n, Over -> GaussianIntegers)tests whether $n$ is prime in $\mathbb{Z}[i]$; a complex $n$ is always tested there

IsPrime(n, Over -> QuadraticIntegers(d))tests whether $n$ is prime in the ring of integers of $\mathbb{Q}(\sqrt d)$, where an irreducible need not be prime

SageMathis_prime(d)✓↗SymPyisprime(d)↗Oscaris_prime(ZZ(d))Juliais_prime(ZZ(d))Rustis_prime(d)

Typed signatures

Type	Package	Applies
(number | quadratic_integer, any*) -> boolean	number-theoryreplaces compute-engine	always
(number) -> boolean	compute-engine	always

Domain: Number theory

Details

• A prime has no positive divisors other than 1 and itself; 1 itself is not prime.
• Returns False unless n is provably prime -- there's no third "unknown" outcome.
• Threads element-wise over a list argument.
• A negative n is not prime: compute-engine rules IsPrime(-7) False, a prime being a natural number. Wolfram's PrimeQ counts a prime's associates and answers True.

Examples

28 more kept as data, checked against the oracles

Basic #

1 is not prime by definition

live ↗

In$\mathrm{IsPrime}(1)$Out$\mathrm{False}$

2 is the only even prime

live ↗

In$\mathrm{IsPrime}(2)$Out$\mathrm{True}$

live ↗

In$\mathrm{IsPrime}(13)$Out$\mathrm{True}$

live ↗

In$\mathrm{IsPrime}(4)$Out$\mathrm{False}$

live ↗

In$\mathrm{IsPrime}(97)$Out$\mathrm{True}$

Threads element-wise over a list

live ↗

In$\mathrm{IsPrime}(\bigl\lbrack1, 2, 3, 4, 5, 6\bigr\rbrack)$Out$\bigl\lbrack\mathrm{False}, \mathrm{True}, \mathrm{True}, \mathrm{False}, \mathrm{True}, \mathrm{False}\bigr\rbrack$

live ↗

In$\mathrm{IsPrime}(5)$Out$\mathrm{True}$

Scope #

-7 is not prime: a prime is a natural number, though Wolfram's PrimeQ counts its associate 7

live ↗

In$\mathrm{IsPrime}(-7)$Out$\mathrm{False}$

a Gaussian prime: its norm 5 is prime

live ↗

In$\mathrm{IsPrime}(2+i)$Out$\mathrm{True}$

$5 = (2 + i)(2 - i)$ splits in $\mathbb{Z}[i]$

live ↗

In$\mathrm{IsPrime}(5, \mathrm{Rule}(\mathrm{Over}, \mathrm{GaussianIntegers}))$Out$\mathrm{False}$

Large integers: $10^{3000}+1$ is divisible by $10^8+1$

live ↗

In$\mathrm{IsPrime}(10^{3\,000}+1)$Out$\mathrm{False}$

Applications #

A common choice of prime modulus for hashing, just above $10^9$

live ↗

In$\mathrm{IsPrime}(1\,000\,000\,007)$Out$\mathrm{True}$

A Fermat prime, $2^8+1$

live ↗

In$\mathrm{IsPrime}(257)$Out$\mathrm{True}$

The Fermat number $F_7$ is composite

live ↗

In$\mathrm{IsPrime}(1+2^{128})$Out$\mathrm{False}$

Prime powers that are not primes

live ↗

In$\mathrm{Filter}(1..100, \operatorname{\_1}↦\mathrm{IsPrimePower}(\operatorname{\_1})∧¬\mathrm{IsPrime}(\operatorname{\_1}))$Out$\bigl\lbrack4, 8, 9, 16, 25, 27, 32, 49, 64, 81\bigr\rbrack$

Properties #

an odd prime stays prime in $\mathbb{Z}[i]$ exactly when $p \equiv 3 \pmod 4$

live ↗

In$\mathrm{IsPrime}(\bigl\lbrack2, 3, 5, 7, 11, 13\bigr\rbrack, \mathrm{Rule}(\mathrm{Over}, \mathrm{GaussianIntegers}))$Out$\bigl\lbrack\mathrm{False}, \mathrm{True}, \mathrm{False}, \mathrm{True}, \mathrm{True}, \mathrm{False}\bigr\rbrack$

37 has no divisor up to $\sqrt{37}$

live ↗

In$\mathrm{IsPrime}(37)$Out$\mathrm{True}$

29, one of a twin pair with 31

live ↗

In$\mathrm{IsPrime}(29)$Out$\mathrm{True}$

17, a Fermat prime $2^4+1$

live ↗

In$\mathrm{IsPrime}(17)$Out$\mathrm{True}$

Composite: $2^2\cdot 3$

live ↗

In$\mathrm{IsPrime}(12)$Out$\mathrm{False}$

23, the ninth prime

live ↗

In$\mathrm{IsPrime}(23)$Out$\mathrm{True}$

Composite: $2^3\cdot 3$

live ↗

In$\mathrm{IsPrime}(24)$Out$\mathrm{False}$

Threads over a list

live ↗

In$\mathrm{IsPrime}(\bigl\lbrack7, 11\bigr\rbrack)$Out$\bigl\lbrack\mathrm{True}, \mathrm{True}\bigr\rbrack$

Threads over a list; 2 is the even prime

live ↗

In$\mathrm{IsPrime}(\bigl\lbrack5, 7, 2\bigr\rbrack)$Out$\bigl\lbrack\mathrm{True}, \mathrm{True}, \mathrm{True}\bigr\rbrack$

19, the eighth prime

live ↗

In$\mathrm{IsPrime}(19)$Out$\mathrm{True}$

A prime is its own only prime divisor

live ↗

In$\mathrm{DivisorSum}(19, \operatorname{\_1}↦\operatorname{\_1}, \mathrm{IsPrime})$Out$19$

live ↗

In$\mathrm{Filter}(\mathrm{Divisors}(625), \mathrm{IsPrime})$Out$\bigl\lbrack5\bigr\rbrack$

live ↗

In$\mathrm{Filter}(\mathrm{Divisors}(2\,434\,500), \mathrm{IsPrime})$Out$\bigl\lbrack2, 3, 5, 541\bigr\rbrack$

live ↗

In$\mathrm{Filter}(\mathrm{Divisors}(65), \mathrm{IsPrime})$Out$\bigl\lbrack5, 13\bigr\rbrack$

Possible issues #

Non-integers are not prime

live ↗

In$\mathrm{IsPrime}(\frac{1}{2})$Out$\mathrm{False}$

A symbol stays unevaluated

live ↗

In$\mathrm{IsPrime}(x)$Out$\mathrm{IsPrime}(x)$

Neat examples #

The Mersenne prime $2^{31}-1$

live ↗

In$\mathrm{IsPrime}(2^{31}-1)$Out$\mathrm{True}$

The Fermat number $F_5=2^{32}+1$ is composite: 641 divides it

live ↗

In$\mathrm{IsPrime}(2^{32}+1)$Out$\mathrm{False}$

About

Examples	61
Checked against	Wolfram Language 58 agree3 differSageMath 42 agree1 errorSymPy 26 agree17 errormathlib4 23 agree12 errorOscar 15 agree5 errorJulia 30 agree12 errorRust 24 agree8 error
Crosswalk	Wikipedia ×2MathWorld ×2WikidataEncyclopedia of MathematicsnLabBritannicaOEISWolfram LanguageSageMathSymPyOscarJuliaRustRosetta Code

Implementation

mappedwolframpackages/oracle/src/mappings.ts

mappedsympypackages/oracle/src/mappings.ts

mappedsagepackages/oracle/src/mappings.ts

mappedoscarpackages/oracle/src/mappings.ts

mappedjuliapackages/oracle/src/mappings.ts

mappedmathlib4packages/oracle/src/mappings.ts

mappedrustpackages/oracle/src/mappings.ts

See also: FactorInteger, NextPrime