Prime Number Program in C, C++, Java, Python, C#, PHP and JavaScript

To prove that 2,147,483,647 is prime, a loop that tries every divisor up to half the number performs 1,073,741,822 remainder operations. Stopping at the square root takes 46,339. Skipping multiples of 2 and 3 as well brings it to 15,448, about 70,000 times fewer than the first loop. A second mistake is just as common and harder to spot: written as i * i <= n with int, the square-root loop overflows on this number and reported it as not prime in all four builds tried.

This guide builds a correct primality test and the Sieve of Eratosthenes, explains why each bound works, and gives the same program in C, C++, Java, Python, C#, PHP and JavaScript, followed by Miller–Rabin for numbers too large for trial division. The C code was compiled with GCC 13.3 and Clang 18.1.3 under -std=c11 and -std=c17, and the C++ code under -std=c++17 and -std=c++20, all with -Wall -Wextra -pedantic and no warnings. The other five versions ran on OpenJDK 21 (--release 17 -Xlint:all), Python 3.11 (mypy --strict and ruff clean), .NET 10 (analyzer warnings as errors), PHP 8.4 and Node.js 22, all on Ubuntu 24.04. All seven print byte-identical output, and every output block below is captured verbatim. The code is in seven GitHub repositories whose workflows run the tests on each commit, including Windows and macOS jobs that were not run on the test machine.

What Is a Prime Number?

A prime number is a whole number greater than 1 whose only positive divisors are 1 and itself. 2, 3, 5, 7 and 11 are prime; 4, 6, 8, 9 and 91 (7 × 13) are not. 1 is not prime, and 2 is the only even prime. A whole number greater than 1 that is not prime is called composite.

Excluding 1 is a convention with a reason: it keeps the factorization of every whole number greater than 1 into primes unique. If 1 were prime, 6 could be written as 2 × 3, 1 × 2 × 3, 1 × 1 × 2 × 3 and so on. There are 25 primes below 100 and 168 below 1,000, and they thin out slowly: there are 664,579 below ten million. Those counts are the prime-counting function π(x), and the programs below reproduce them.

How to Check Whether a Number Is Prime

Trial division tests divisors in order until one divides the number or the candidates run out:

1. If n is less than 2, it is not prime. That covers 1, 0 and every negative number.
2. If n is 2 or 3, it is prime.
3. If n is divisible by 2 or 3, it is not prime.
4. Try divisors of the form 6k − 1 and 6k + 1 (5 and 7, 11 and 13, 17 and 19, …) while the divisor is no larger than √n. If one divides n, it is not prime.
5. If none does, n is prime.

Step 1 is the one short programs most often leave out. Step 4 is where the speed comes from.

Why the Square Root Is Enough

If n = a × b and both factors were larger than √n, their product would be larger than n. So every composite number has a divisor no larger than its square root, and a loop that has found none by then can stop. For n = 2,147,483,647 (2³¹ − 1, the largest value of a 32-bit int, and prime), √n is about 46,341.

Every prime above 3 has the form 6k − 1 or 6k + 1, because the other four remainders after dividing by 6 give a number divisible by 2 or 3. After testing 2 and 3 directly, the loop can try just two candidates in every six. src/divisions.c in the C repository counts the remainder operations each bound needs for 2³¹ − 1:

divisors tried                remainders
2 .. n/2                      1073741822
2 .. sqrt(n)                       46339
2, then odd .. sqrt(n)             23170
2, 3, then 6k +/- 1                15448

Each count matches the arithmetic exactly: ⌊n/2⌋ − 1 = 1,073,741,822, then ⌊√n⌋ − 1 = 46,339, then 1 + 23,169 odd divisors = 23,170, then 2 + 2 × 7,723 = 15,448. The 6k ± 1 loop does about a third of the work of trying every divisor to √n, and roughly one seventy-thousandth of trying every divisor to n/2.

Four Mistakes That Pass a Quick Test

Each of these gives the right answer for 7, 11 and 97, which is usually where a first test stops.

1. Treating Numbers Below 2 as Prime

A loop from 2 to n/2 never runs when n is below 4, so a function that returns “prime” when the loop finds nothing says so for 1, for 0 and for every negative number:

#include <stdbool.h>
#include <stdio.h>

bool naive_is_prime(int n)
{
    for (int i = 2; i <= n / 2; i++)
        if (n % i == 0)
            return false;
    return true;             /* reached for 0, 1 and every negative n too */
}

int main(void)
{
    const int samples[] = { -7, 0, 1, 2, 3, 4 };
    for (int k = 0; k < 6; k++)
        printf("%d: %s\n", samples[k], naive_is_prime(samples[k]) ? "prime" : "not prime");
    return 0;
}

Output:

-7: prime
0: prime
1: prime
2: prime
3: prime
4: not prime

2 and 3 are right by accident; −7, 0 and 1 are wrong. The n < 2 check comes first in every version below, and the test suites check −7, −1, 0, 1 and the most negative 64-bit value.

2. Overflowing i * i

i * i <= n is the natural way to write “up to the square root” without calling sqrt(). With int and n = 2,147,483,647, the loop reaches i = 46,341, whose square does not fit in an int. Signed overflow is undefined behaviour in C and C++:

#include <stdbool.h>
#include <stdio.h>

bool is_prime_int(int n)
{
    if (n < 2)
        return false;
    for (int i = 2; i * i <= n; i++)      /* i * i overflows int for n near INT_MAX */
        if (n % i == 0)
            return false;
    return true;
}

int main(void)
{
    printf("is_prime_int(2147483647) = %s\n", is_prime_int(2147483647) ? "true" : "false");
    return 0;
}

UndefinedBehaviorSanitizer names the problem:

overflow.c:8:23: runtime error: signed integer overflow: 46341 * 46341 cannot be represented in type 'int'

Without the sanitizer, all four builds tried printed is_prime_int(2147483647) = false, which is wrong. They got there differently. GCC at -O0 and Clang at -O0 and -O2 ran for about 4.5 seconds, because the product wrapped to a negative number that passed the test and the loop ran on until i reached n itself and divided it. GCC at -O2 answered in about a millisecond, which is consistent with the optimizer having compiled the loop on the assumption that the overflow cannot happen. Small inputs never reach the overflow, so a test that uses them passes.

There are two fixes, and the programs below use both: compare with i <= n / i, which cannot overflow, and use a 64-bit integer type, so inputs up to 2³¹ − 1 are nowhere near the limit. The same kind of limit comes up when the Fibonacci series outgrows its integer type.

3. Trusting scanf("%d")

scanf("%d", &n) returns the number of values it converted, and a program that ignores it goes on using n whether or not anything was read. Given the input abc, n stays uninitialized, and the program prints a verdict about whatever value happened to be in memory; Valgrind reports Conditional jump or move depends on uninitialised value(s). check_prime.c in the C section reads a whole line with fgets(), converts it with strtoll(), and rejects anything that is not a complete 64-bit integer.

4. A Return Value That Means the Opposite of Its Name

A function called is_prime that returns 0 for a prime and 1 for a composite works as long as every caller remembers the reversal, and every caller has to. The C versions below return bool, from <stdbool.h>, and true means prime.

Listing Primes: the Sieve of Eratosthenes

To find every prime below a limit, testing each number separately repeats work: every even number is divided by 2 again and again. The Sieve of Eratosthenes turns the problem around. It starts with every number from 2 marked as prime, then, for each number p still marked, crosses out p², p² + p, p² + 2p and so on. It starts at p² because every smaller multiple of p has a smaller prime factor and has already been crossed out. It stops once p² passes the limit.

The sieve uses no division at all, only additions, and runs in O(n log log n) time. Its cost is memory: one flag per number, a byte each in the C, Python, PHP and JavaScript versions below (and in Java’s boolean[] on the usual JVMs), and one bit each in the C++ std::vector<bool> and C# BitArray versions. For ten million numbers that is 10 MB or 1.25 MB. The flags are a plain array indexed by the number itself; see arrays in C and C++ for the layout.

How much faster is the sieve?

primes below 10000000: 664579 by trial division, 664579 by the sieve
trial division:    2.079 s
sieve:             0.051 s

The sieve was about 40 times faster at ten million. One run at a hundred million took 54.9 s by trial division and 0.88 s by the sieve, about 60 times, because trial division’s cost per number grows with √n while the sieve’s grows only with log log n. Both methods found 664,579 primes below ten million and 5,761,455 below a hundred million, the published values of π(x). These are single runs on one virtual machine, not averages, with no warm-up discarded and no CPU pinning; the hundred-million run used an earlier build of the same program that read the wall clock. The ratio is the finding, not the absolute seconds.

A sieve is the right tool when you need many primes in a range; trial division is the right tool for checking a handful of numbers. Checking one number with a sieve means building a table as large as the number.

Implementations

Every version has the same two functions, is_prime() and sieve(), and the same demo, in the same spirit as the multi-language quicksort guide, which prints this, byte for byte, in all seven languages:

primes below 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
primes below 1000: 168
primes below 1000000: 78498
is_prime: -7 false, 0 false, 1 false, 2 true, 91 false, 97 true
is_prime(2147483647) = true
is_prime(1000000007) = true

C

/* primes.c - test one number for primality, and list primes with the
 * Sieve of Eratosthenes.
 * Build: gcc -std=c11 -Wall -Wextra -pedantic primes.c -o primes
 */
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

/* Trial division by 2, 3 and then 6k - 1 and 6k + 1 up to sqrt(n).
 * i <= n / i is the overflow-safe form of i * i <= n. */
bool is_prime(int64_t n)
{
    if (n < 2)
        return false;
    if (n < 4)
        return true;                        /* 2 and 3 */
    if (n % 2 == 0 || n % 3 == 0)
        return false;
    for (int64_t i = 5; i <= n / i; i += 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    return true;
}

/* Returns a heap-allocated array of limit flags where flags[k] is true when k is
 * prime, or NULL if memory runs out. The caller frees it. */
bool *sieve(size_t limit)
{
    if (limit > SIZE_MAX / sizeof(bool))           /* byte count would overflow */
        return NULL;
    bool *flags = calloc(limit > 0 ? limit : 1, sizeof *flags);
    if (flags == NULL)
        return NULL;
    for (size_t k = 0; k < limit; ++k)
        flags[k] = k >= 2;
    for (size_t p = 2; limit > 0 && p <= (limit - 1) / p; ++p) {
        if (!flags[p])
            continue;
        for (size_t m = p * p; m < limit; m += p)   /* smaller multiples */
            flags[m] = false;                        /* are already crossed */
    }
    return flags;
}

static size_t count_primes_below(size_t limit)
{
    bool *flags = sieve(limit);
    if (flags == NULL) {
        fputs("out of memory\n", stderr);
        exit(EXIT_FAILURE);
    }
    size_t count = 0;
    for (size_t k = 0; k < limit; ++k)
        count += flags[k];
    free(flags);
    return count;
}

int main(void)
{
    bool *flags = sieve(100);
    if (flags == NULL)
        return EXIT_FAILURE;
    printf("primes below 100:");
    for (size_t k = 0; k < 100; ++k)
        if (flags[k])
            printf(" %zu", k);
    printf("\n");
    free(flags);

    printf("primes below 1000: %zu\n", count_primes_below(1000));
    printf("primes below 1000000: %zu\n", count_primes_below(1000000));

    const int64_t samples[] = { -7, 0, 1, 2, 91, 97 };
    printf("is_prime:");
    for (size_t k = 0; k < sizeof samples / sizeof samples[0]; ++k)
        printf(" %lld %s%s", (long long)samples[k],
               is_prime(samples[k]) ? "true" : "false",
               k + 1 < sizeof samples / sizeof samples[0] ? "," : "\n");
    printf("is_prime(2147483647) = %s\n", is_prime(2147483647) ? "true" : "false");
    printf("is_prime(1000000007) = %s\n", is_prime(1000000007) ? "true" : "false");
    return EXIT_SUCCESS;
}

is_prime() takes int64_t, so it handles every value up to 9,223,372,036,854,775,807, and i <= n / i keeps the bound check overflow-free even there. sieve() checks that limit * sizeof(bool) fits in a size_t before calling calloc(), rather than relying on calloc() to catch the overflow: glibc does, but it is cheap to state yourself (SEI CERT rule MEM07-C recommends it). With sizeof(bool) equal to 1, as on the mainstream compilers, the check can never fire; it keeps the code correct where that is not true. The function returns NULL rather than crashing when memory runs out.

For the classic “enter a number” program, check_prime.c adds input validation:

/* check_prime.c - read one number and say whether it is prime.
 * Build: gcc -std=c11 -Wall -Wextra -pedantic check_prime.c -o check_prime
 */
#include <errno.h>
#include <inttypes.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

static bool is_prime(int64_t n)
{
    if (n < 2)
        return false;
    if (n < 4)
        return true;
    if (n % 2 == 0 || n % 3 == 0)
        return false;
    for (int64_t i = 5; i <= n / i; i += 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    return true;
}

int main(void)
{
    char line[64];
    printf("Enter an integer: ");
    fflush(stdout);                              /* show the prompt before reading */
    if (fgets(line, sizeof line, stdin) == NULL) {
        fputs("no input\n", stderr);
        return EXIT_FAILURE;
    }

    char *end;
    errno = 0;
    long long value = strtoll(line, &end, 10);   /* long long: at least 64 bits */
    bool no_digits = (end == line);              /* check before skipping spaces */
    while (*end == ' ' || *end == '\t' || *end == '\n' || *end == '\r')
        end++;
    if (no_digits || *end != '\0') {
        fprintf(stderr, "not an integer\n");
        return EXIT_FAILURE;
    }
    if (errno == ERANGE) {
        fprintf(stderr, "out of range for a 64-bit integer\n");
        return EXIT_FAILURE;
    }

    int64_t n = (int64_t)value;
    printf("%" PRId64 " is %s\n", n, is_prime(n) ? "prime" : "not prime");
    return EXIT_SUCCESS;
}

$ echo "97" | ./check_prime
Enter an integer: 97 is prime
$ echo "91" | ./check_prime
Enter an integer: 91 is not prime
$ echo "1" | ./check_prime
Enter an integer: 1 is not prime
$ echo "-7" | ./check_prime
Enter an integer: -7 is not prime
$ echo "2147483647" | ./check_prime
Enter an integer: 2147483647 is prime
$ echo "abc" | ./check_prime
Enter an integer: not an integer
(exit status 1)
$ echo "12abc" | ./check_prime
Enter an integer: not an integer
(exit status 1)
$ echo "99999999999999999999" | ./check_prime
Enter an integer: out of range for a 64-bit integer
(exit status 1)
$ echo "" | ./check_prime
Enter an integer: not an integer
(exit status 1)

The empty line is worth a test of its own. The first version of this program skipped trailing whitespace before checking whether strtoll() had read any digits, and the skip moved past the newline, so an empty line was read as 0 and reported as “0 is not prime”. The CI step that feeds invalid input caught it. The check now happens before the skip.

C++

// primes.cpp - test one number for primality, and list primes with the
// Sieve of Eratosthenes.
// Build: g++ -std=c++17 -Wall -Wextra -pedantic primes.cpp -o primes
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <iterator>
#include <vector>

// Trial division by 2, 3 and then 6k - 1 and 6k + 1 up to sqrt(n).
// i <= n / i is the overflow-safe form of i * i <= n.
constexpr bool is_prime(std::int64_t n)
{
    if (n < 2)
        return false;
    if (n < 4)
        return true;                         // 2 and 3
    if (n % 2 == 0 || n % 3 == 0)
        return false;
    for (std::int64_t i = 5; i <= n / i; i += 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    return true;
}

// constexpr lets the compiler check known values while it builds.
static_assert(is_prime(2147483647), "2^31 - 1 is prime");
static_assert(!is_prime(1) && !is_prime(91), "1 and 7 * 13 are not prime");

// flags[k] is true when k is prime, for 0 <= k < limit.
std::vector<bool> sieve(std::size_t limit)
{
    std::vector<bool> flags(limit, true);
    for (std::size_t k = 0; k < limit && k < 2; ++k)
        flags[k] = false;                    // 0 and 1
    for (std::size_t p = 2; limit > 0 && p <= (limit - 1) / p; ++p) {
        if (!flags[p])
            continue;
        for (std::size_t m = p * p; m < limit; m += p)
            flags[m] = false;
    }
    return flags;
}

std::size_t count_primes_below(std::size_t limit)
{
    std::size_t count = 0;
    for (bool f : sieve(limit))
        count += f;
    return count;
}

int main()
{
    const std::vector<bool> flags = sieve(100);
    std::cout << "primes below 100:";
    for (std::size_t k = 0; k < flags.size(); ++k)
        if (flags[k])
            std::cout << ' ' << k;
    std::cout << '\n';

    std::cout << "primes below 1000: " << count_primes_below(1000) << '\n';
    std::cout << "primes below 1000000: " << count_primes_below(1000000) << '\n';

    const std::int64_t samples[] = {-7, 0, 1, 2, 91, 97};
    std::cout << "is_prime:" << std::boolalpha;
    for (std::size_t k = 0; k < std::size(samples); ++k)
        std::cout << ' ' << samples[k] << ' ' << is_prime(samples[k])
                  << (k + 1 < std::size(samples) ? "," : "\n");
    std::cout << "is_prime(2147483647) = " << is_prime(2147483647) << '\n';
    std::cout << "is_prime(1000000007) = " << is_prime(1000000007) << '\n';
    return 0;
}

is_prime() is constexpr, so the two static_assert lines run it while the program compiles. Deleting the n < 2 check makes the build itself fail:

src/primes.cpp:26:15: error: static assertion failed: 1 and 7 * 13 are not prime

std::vector<bool> stores one bit per flag rather than one byte. It is not a real container of bool (its operator[] returns a proxy object rather than a bool&), but for a sieve, which only reads and writes flags by index, that difference does not matter.

Java

/** Test one number for primality, and list primes with the Sieve of Eratosthenes. */
public final class Primes {
    private Primes() { }

    /** Trial division by 2, 3 and then 6k - 1 and 6k + 1 up to sqrt(n).
     *  i <= n / i is the overflow-safe form of i * i <= n. */
    public static boolean isPrime(long n) {
        if (n < 2) {
            return false;
        }
        if (n < 4) {
            return true;                       // 2 and 3
        }
        if (n % 2 == 0 || n % 3 == 0) {
            return false;
        }
        for (long i = 5; i <= n / i; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }

    /** flags[k] is true when k is prime, for 0 <= k < limit. */
    public static boolean[] sieve(int limit) {
        boolean[] flags = new boolean[limit];
        for (int k = 2; k < limit; k++) {
            flags[k] = true;
        }
        for (int p = 2; limit > 0 && p <= (limit - 1) / p; p++) {
            if (!flags[p]) {
                continue;
            }
            for (long m = (long) p * p; m < limit; m += p) {   // long: m + p may pass 2^31 - 1
                flags[(int) m] = false;
            }
        }
        return flags;
    }

    public static int countPrimesBelow(int limit) {
        int count = 0;
        for (boolean f : sieve(limit)) {
            if (f) {
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        StringBuilder out = new StringBuilder("primes below 100:");
        boolean[] flags = sieve(100);
        for (int k = 0; k < flags.length; k++) {
            if (flags[k]) {
                out.append(' ').append(k);
            }
        }
        System.out.println(out);
        System.out.println("primes below 1000: " + countPrimesBelow(1000));
        System.out.println("primes below 1000000: " + countPrimesBelow(1000000));

        long[] samples = {-7, 0, 1, 2, 91, 97};
        StringBuilder line = new StringBuilder("is_prime:");
        for (int k = 0; k < samples.length; k++) {
            line.append(' ').append(samples[k]).append(' ').append(isPrime(samples[k]))
                .append(k + 1 < samples.length ? "," : "");
        }
        System.out.println(line);
        System.out.println("is_prime(2147483647) = " + isPrime(2147483647L));
        System.out.println("is_prime(1000000007) = " + isPrime(1000000007L));
    }
}

isPrime() takes a long, Java’s 64-bit type. In sieve(), the multiple m is a long too: with an int, m += p could pass Integer.MAX_VALUE and wrap to a negative index for a limit close to 2³¹. For numbers beyond long, BigInteger has a built-in test, isProbablePrime(certainty), whose false-positive probability is at most 1/2^certainty.

Python

"""Test one number for primality, and list primes with the Sieve of Eratosthenes.

Run:  python3 primes.py
"""
from math import isqrt


def is_prime(n: int) -> bool:
    """Trial division by 2, 3 and then 6k - 1 and 6k + 1 up to sqrt(n)."""
    if n < 2:
        return False
    if n < 4:
        return True                      # 2 and 3
    if n % 2 == 0 or n % 3 == 0:
        return False
    for i in range(5, isqrt(n) + 1, 6):  # isqrt is exact for any int
        if n % i == 0 or n % (i + 2) == 0:
            return False
    return True


def sieve(limit: int) -> bytearray:
    """flags[k] is 1 when k is prime, for 0 <= k < limit."""
    flags = bytearray([1]) * limit
    flags[:2] = bytearray(min(limit, 2))  # 0 and 1 are not prime
    for p in range(2, isqrt(max(limit - 1, 0)) + 1):
        if flags[p]:
            flags[p * p::p] = bytearray(len(range(p * p, limit, p)))
    return flags


def count_primes_below(limit: int) -> int:
    return sum(sieve(limit))


def main() -> None:
    flags = sieve(100)
    print("primes below 100:", " ".join(str(k) for k in range(100) if flags[k]))
    print("primes below 1000:", count_primes_below(1000))
    print("primes below 1000000:", count_primes_below(1_000_000))
    samples = [-7, 0, 1, 2, 91, 97]
    print("is_prime:", ", ".join(f"{n} {str(is_prime(n)).lower()}" for n in samples))
    print("is_prime(2147483647) =", str(is_prime(2147483647)).lower())
    print("is_prime(1000000007) =", str(is_prime(1000000007)).lower())


if __name__ == "__main__":
    main()

Python integers have no fixed width, so there is nothing to overflow, and math.isqrt() returns the exact integer square root of any integer. The sieve is a bytearray, and flags[p * p::p] = … crosses out every multiple of p in a single slice assignment, which runs inside the interpreter’s C code rather than as a Python loop.

C#

using System;
using System.Collections;
using System.Linq;

namespace MyCPlus.Primes;

public static class Primes
{
    // Trial division by 2, 3 and then 6k - 1 and 6k + 1 up to sqrt(n).
    // i <= n / i is the overflow-safe form of i * i <= n.
    public static bool IsPrime(long n)
    {
        if (n < 2)
            return false;
        if (n < 4)
            return true;                         // 2 and 3
        if (n % 2 == 0 || n % 3 == 0)
            return false;
        for (long i = 5; i <= n / i; i += 6)
        {
            if (n % i == 0 || n % (i + 2) == 0)
                return false;
        }
        return true;
    }

    // flags[k] is true when k is prime, for 0 <= k < limit.
    public static BitArray Sieve(int limit)
    {
        var flags = new BitArray(limit, true);
        for (int k = 0; k < Math.Min(limit, 2); k++)
            flags[k] = false;                    // 0 and 1
        for (int p = 2; limit > 0 && p <= (limit - 1) / p; p++)
        {
            if (!flags[p])
                continue;
            for (long m = (long)p * p; m < limit; m += p)   // long: m + p may pass int.MaxValue
                flags[(int)m] = false;
        }
        return flags;
    }

    public static int CountPrimesBelow(int limit) => Sieve(limit).Cast<bool>().Count(f => f);

    public static void Main()
    {
        BitArray flags = Sieve(100);
        Console.WriteLine("primes below 100: " +
            string.Join(' ', Enumerable.Range(0, 100).Where(k => flags[k])));
        Console.WriteLine($"primes below 1000: {CountPrimesBelow(1000)}");
        Console.WriteLine($"primes below 1000000: {CountPrimesBelow(1_000_000)}");

        long[] samples = [-7, 0, 1, 2, 91, 97];
        Console.WriteLine("is_prime: " +
            string.Join(", ", samples.Select(n => $"{n} {(IsPrime(n) ? "true" : "false")}")));
        Console.WriteLine($"is_prime(2147483647) = {(IsPrime(2147483647) ? "true" : "false")}");
        Console.WriteLine($"is_prime(1000000007) = {(IsPrime(1000000007) ? "true" : "false")}");
    }
}

IsPrime() takes a long. The sieve uses System.Collections.BitArray, one bit per number. The file builds as a console project (dotnet new console, then replace Program.cs), and the collection expressions ([-7, 0, 1, 2, 91, 97]) need C# 12, which the .NET 8 SDK and later provide.

PHP

<?php
// primes.php - test one number for primality, and list primes with the
// Sieve of Eratosthenes. Run: php primes.php
declare(strict_types=1);

// Trial division by 2, 3 and then 6k - 1 and 6k + 1 up to sqrt(n).
// $i <= intdiv($n, $i) is the overflow-safe form of $i * $i <= $n.
function is_prime(int $n): bool
{
    if ($n < 2) {
        return false;
    }
    if ($n < 4) {
        return true;                            // 2 and 3
    }
    if ($n % 2 === 0 || $n % 3 === 0) {
        return false;
    }
    for ($i = 5; $i <= intdiv($n, $i); $i += 6) {
        if ($n % $i === 0 || $n % ($i + 2) === 0) {
            return false;
        }
    }
    return true;
}

// A string of $limit bytes: "1" at offset k when k is prime. One byte per
// number costs far less memory than a PHP array of booleans.
function sieve(int $limit): string
{
    $flags = str_repeat('1', $limit);
    for ($k = 0; $k < min($limit, 2); $k++) {
        $flags[$k] = '0';                       // 0 and 1
    }
    for ($p = 2; $limit > 0 && $p <= intdiv($limit - 1, $p); $p++) {
        if ($flags[$p] === '0') {
            continue;
        }
        for ($m = $p * $p; $m < $limit; $m += $p) {
            $flags[$m] = '0';
        }
    }
    return $flags;
}

function count_primes_below(int $limit): int
{
    return substr_count(sieve($limit), '1');
}

function main(): void
{
    $flags = sieve(100);
    $list = [];
    for ($k = 0; $k < 100; $k++) {
        if ($flags[$k] === '1') {
            $list[] = $k;
        }
    }
    echo 'primes below 100: ', implode(' ', $list), "\n";
    echo 'primes below 1000: ', count_primes_below(1000), "\n";
    echo 'primes below 1000000: ', count_primes_below(1000000), "\n";
    $parts = [];
    foreach ([-7, 0, 1, 2, 91, 97] as $n) {
        $parts[] = $n . ' ' . (is_prime($n) ? 'true' : 'false');
    }
    echo 'is_prime: ', implode(', ', $parts), "\n";
    echo 'is_prime(2147483647) = ', is_prime(2147483647) ? 'true' : 'false', "\n";
    echo 'is_prime(1000000007) = ', is_prime(1000000007) ? 'true' : 'false', "\n";
}

if (PHP_SAPI === 'cli' && realpath($argv[0]) === __FILE__) {
    main();
}

PHP integers are 64-bit on 64-bit builds (PHP_INT_SIZE is 8), which the test suite checks. intdiv() gives the integer quotient for the $i <= intdiv($n, $i) bound. The sieve is a string of '1' and '0' characters rather than an array: a PHP array stores each element as a separate value with its own overhead, while a string stores one byte per number, and substr_count() counts the primes without a loop in PHP code.

JavaScript

// primes.js - test one number for primality, and list primes with the
// Sieve of Eratosthenes. Run: node primes.js
import { pathToFileURL } from 'node:url';

// Trial division by 2, 3 and then 6k - 1 and 6k + 1 up to sqrt(n).
// Numbers are doubles, exact only up to Number.MAX_SAFE_INTEGER (2^53 - 1),
// so larger inputs are refused rather than answered wrongly.
export function isPrime(n) {
  if (!Number.isSafeInteger(n)) {
    throw new RangeError(`isPrime needs a safe integer, got ${n}`);
  }
  if (n < 2) return false;
  if (n < 4) return true;                       // 2 and 3
  if (n % 2 === 0 || n % 3 === 0) return false;
  for (let i = 5; i * i <= n; i += 6) {         // i * i stays exact here
    if (n % i === 0 || n % (i + 2) === 0) return false;
  }
  return true;
}

// flags[k] is 1 when k is prime, for 0 <= k < limit.
export function sieve(limit) {
  const flags = new Uint8Array(limit).fill(1);
  flags.fill(0, 0, Math.min(limit, 2));         // 0 and 1
  for (let p = 2; p * p < limit; p++) {
    if (!flags[p]) continue;
    for (let m = p * p; m < limit; m += p) flags[m] = 0;
  }
  return flags;
}

export function countPrimesBelow(limit) {
  return sieve(limit).reduce((sum, f) => sum + f, 0);
}

export function main() {
  const flags = sieve(100);
  const list = [];
  for (let k = 0; k < 100; k++) if (flags[k]) list.push(k);
  console.log(`primes below 100: ${list.join(' ')}`);
  console.log(`primes below 1000: ${countPrimesBelow(1000)}`);
  console.log(`primes below 1000000: ${countPrimesBelow(1000000)}`);
  const samples = [-7, 0, 1, 2, 91, 97];
  console.log(`is_prime: ${samples.map((n) => `${n} ${isPrime(n)}`).join(', ')}`);
  console.log(`is_prime(2147483647) = ${isPrime(2147483647)}`);
  console.log(`is_prime(1000000007) = ${isPrime(1000000007)}`);
}

if (process.argv[1] && import.meta.url === pathToFileURL(process.argv[1]).href) {
  main();
}

JavaScript numbers are 64-bit floating-point values, exact for integers only up to Number.MAX_SAFE_INTEGER, 2⁵³ − 1. Beyond that, n % i works on a rounded value, so isPrime() throws a RangeError instead of answering. Within the safe range i * i stays exact for every divisor the loop reaches, and the test suite confirms that 9,007,199,254,740,881, the largest prime below 2⁵³, is accepted. For larger values, the same algorithm works on BigInt. The sieve is a Uint8Array, one byte per number.

Very Large Numbers: Miller–Rabin

Trial division slows down with √n. Checking 9,223,372,036,854,775,783, the largest prime below 2⁶³, took 3.6 s in C (two runs on the same machine as the benchmark). For numbers of that size and beyond, programs use the Miller–Rabin test: instead of searching for a divisor, it checks a property that every prime has, using modular exponentiation with a handful of bases. With arbitrary bases the test is probabilistic, but for every n below 2⁶⁴ the first twelve primes, 2 through 37, are enough, and the answer is exact: the smallest number that fools all twelve is 318,665,857,834,031,151,167,461, found by Sorenson and Webster, which is larger than 2⁶⁴.

"""Deterministic Miller-Rabin test for integers below 2**64.

Testing the first twelve primes as bases is enough for every n < 2**64.
Run:  python3 miller_rabin.py
"""
from time import perf_counter

BASES = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37)


def is_prime_mr(n: int) -> bool:
    if n < 2:
        return False
    for p in BASES:
        if n % p == 0:
            return n == p
    if n >= 2**64:
        raise ValueError("these bases are proven only for n < 2**64")
    d, s = n - 1, 0
    while d % 2 == 0:                  # n - 1 = d * 2**s with d odd
        d //= 2
        s += 1
    for a in BASES:
        x = pow(a, d, n)               # modular exponentiation
        if x in (1, n - 1):
            continue
        for _ in range(s - 1):
            x = x * x % n
            if x == n - 1:
                break
        else:
            return False               # a proves n composite
    return True


if __name__ == "__main__":
    n = 9223372036854775783            # the largest prime below 2**63
    start = perf_counter()
    result = is_prime_mr(n)
    print(f"is_prime_mr({n}) = {str(result).lower()} in {(perf_counter() - start) * 1e6:.0f} microseconds")

is_prime_mr(9223372036854775783) = true in 151 microseconds

That is under a millisecond in Python against 3.6 seconds of trial division in C: two different languages, but a gap far too large for the language to explain. Python’s three-argument pow(a, d, n) does the modular exponentiation without ever building the huge intermediate power. The test suite checks this function against trial division for every value below 200,000, confirms that it accepts the largest primes below 2⁶³ and 2⁶⁴, and confirms that it rejects 3,215,031,751 and 3,825,123,056,546,413,051, which fool Miller–Rabin with smaller base sets.

In production code, reach for a library: BigInteger.isProbablePrime() in Java, sympy.isprime() in Python (a third-party package), mpz_probab_prime_p() in GMP for C and C++, or BN_check_prime() in OpenSSL.

Where Prime Numbers Are Used

• Public-key cryptography. RSA keys are built from two large random primes, and its security rests on how hard it is to factor their product. Generating those primes is a Miller–Rabin job: pick a random odd number of the right size, test it, and repeat until one passes.
• Hashing. Some hash-table implementations use a prime number of buckets, so that keys sharing a common factor do not pile into the same few buckets.
• Pseudo-random numbers. Lehmer generators compute each value as the previous one times a constant, modulo a prime; with a well-chosen constant, the prime modulus gives the longest possible period.
• Practice problems. Primality tests and sieves are standard exercises for loops, integer arithmetic and complexity, alongside the top 10 algorithms every programmer should know, which is why the mistakes above are worth knowing by sight.

Key Takeaways

• A prime is a whole number greater than 1 with no divisors except 1 and itself. Check n < 2 first; 1, 0 and negative numbers are not prime.
• Stop at the square root. For 2³¹ − 1 that is 46,339 remainders instead of 1,073,741,822, and 15,448 when only 6k ± 1 candidates are tried.
• Write the bound as i <= n / i and use 64-bit integers. i * i <= n in int overflows on 2³¹ − 1, and all four builds tried gave the wrong answer.
• Use the sieve to list primes. It counted the primes below ten million about 40 times faster than testing each number.
• Validate input instead of trusting scanf("%d"); an empty line is an input too.
• For very large numbers, use Miller–Rabin or a library that implements it: well under a millisecond where trial division needed 3.6 seconds.

Frequently Asked Questions

Conclusion

A prime-number check fits in ten lines, and most of the ways to get it wrong fit in one: a missing n < 2, a bound written as i * i, an input nobody validated. None of them shows up for 7, 11 or 97, which is why the tests here check −7, 0, 1, squares of primes, 2³¹ − 1 and the edges of each language’s integer type, and compare every answer with an independent method.

The same pattern — a direct test for one value, a sieve for many, and a smarter algorithm when the numbers get large — runs through much of algorithm design. More of it is in the algorithms section.

Source Code and Tests

Language	Repository directory	Build
C	mycplus/c-examples › math/prime-numbers
C++	mycplus/cpp-examples › math/prime-numbers
Java	mycplus/java-examples › math/prime-numbers
Python	mycplus/python-examples › math/prime-numbers
C#	mycplus/csharp-examples › math/prime-numbers
PHP	mycplus/php-examples › math/prime-numbers
JavaScript	mycplus/javascript-examples › math/prime-numbers

Each directory has its own README with build commands. The C and C++ versions build with CMake (cmake -S . -B build, cmake --build build, ctest --test-dir build); the others run with their language’s own tools and no third-party packages.

What a green badge means, exactly, in every language:

• Trial division agrees with the sieve on every number below 200,000. The two methods share no code, so agreement is stronger evidence than either passing alone.
• Known values are classified correctly: primes including 2³¹ − 1, 1,000,000,007 and 999,999,999,989; non-primes including negatives, 0, 1, squares of primes, the product of two large primes, and the Carmichael numbers 561 and 1,105.
• The sieve reproduces the published prime counts below 1,000, one million and ten million.
• The demo prints the output shown above, from one expected file shared by all seven repositories.
• Compiler and linter settings: C and C++ with GCC, Clang and MSVC, warnings as errors, and the tests under AddressSanitizer and UndefinedBehaviorSanitizer; Java 17, 21 and 25 with -Xlint:all -Werror; Python 3.10 to 3.14 with ruff and mypy --strict; C# with analyzer warnings as errors on Linux, Windows and macOS; PHP 8.2 to 8.4; Node.js 22 and 24.
• Language-specific checks: C’s check_prime rejects non-numeric, partial, empty and out-of-range input; C’s divisions prints the counts above; Python’s Miller–Rabin matches trial division and rejects the known strong pseudoprimes; JavaScript refuses values it cannot represent exactly.

The builds do not check the timings on this page, which came from one machine.