Is 509 a prime number?

Primality test for 509

509 is prime!

Step-by-step primality test

√509 ≈ 22.56 → testing all candidates up to 22

Every prime > 3 is of the form 6k − 1 or 6k + 1. We test these candidates up to √N by computing the remainder using Euclidean division:

509 mod 2 = 1
509 mod 3 = 2
509 mod 5 = 4
509 mod 7 = 5
509 mod 11 = 3
509 mod 13 = 2
509 mod 17 = 16
509 mod 19 = 15

No divisor found → 509 is prime.

509 is:

  • ✓ prime
  • ✓ odd
  • ✓ a Sophie Germain prime (2 × 509 + 1 = 1,019 is also prime)

Try another number

Try: 2 · 17 · 97 · 127 · 541 · 8191 · 65537

Limit: 2 to 10¹² (1,000,000,000,000). The tool tests up to ~78,500 candidate divisors and returns an answer in milliseconds.

About prime numbers

Why do primes matter?

Prime numbers are the building blocks of all integers. By the Fundamental Theorem of Arithmetic, every integer ≥ 2 can be written as a unique product of primes. Primes also underpin modern cryptography: RSA encryption relies on the fact that multiplying two large primes together is trivial, but factoring the result back is computationally hard.

How common are primes?

Primes become rarer as numbers grow, but they never stop entirely. The Prime Number Theorem (proved independently by Hadamard and de la Vallée Poussin in 1896) states that the count of primes up to N is approximately N ÷ ln(N). Around 10¹², roughly one integer in every 28 is prime — still very common.

Frequently asked questions

A prime number is a positive integer greater than 1 that has exactly two positive divisors: 1 and itself. Examples: 2, 3, 5, 7, 11, 13. A number with more than two divisors (e.g. 6 = 2 × 3) is called composite.
There are 25 prime numbers between 1 and 100: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.
No. The integer 1 is called a unit — it is neither prime nor composite. A prime must have exactly two divisors; 1 has only one (itself).
Yes, 2 is prime — and it is the only even prime. Every other even number is divisible by 2 and is therefore composite.
The tool uses trial division: it tests whether N is divisible by 2, 3, and then all integers of the form 6k − 1 or 6k + 1 up to √N. Any prime greater than 3 must be of one of these two forms, so no candidate is missed. For N = 10¹², this means at most ~78,500 candidates — fast enough to return an answer in milliseconds.
As of 2024, the largest known prime is 2^136,279,841 − 1, a Mersenne prime discovered in October 2024 with over 41 million digits. Such numbers are found with the Lucas–Lehmer primality test and massive distributed computing, not trial division.
Two primes that differ by exactly 2 are called twin primes. Examples: (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43). The Twin Prime Conjecture states there are infinitely many such pairs, but this has never been proved.
A prime p is a Sophie Germain prime if 2p + 1 is also prime (the resulting prime 2p + 1 is called a safe prime). Examples: 2 → 5, 3 → 7, 5 → 11, 11 → 23. They are named after French mathematician Marie-Sophie Germain (1776–1831), who used them in her work toward a proof of Fermat's Last Theorem.

Related tools

Divisors Calculator
Find all divisors of any integer up to 10¹², with factor pairs and divisor count τ(n).
Open tool →
Prime Factorization
Decompose any integer up to 10¹³ into its prime factors.
Open tool →
GCD and LCM Calculator
Greatest Common Divisor and Least Common Multiple for up to 6 integers.
Open tool →

Send your feedback