primacy

# Primacy

Check for and generate prime numbers

## Installation

If [available in Hex](https://hex.pm/docs/publish), the package can be installed
by adding `primacy` to your list of dependencies in `mix.exs`:

```elixir
def deps do
  [
    {:primacy, "~> 0.2.0"}
  ]
end
```

## Usage

```elixir
iex> Primacy.is_prime?(123_456_794_333)
true

iex> Primacy.is_prime?(123_456_794_334)
false

iex> Primacy.primes_near(600, count: 10)
[571, 577, 587, 593, 599, 601, 607, 613, 617, 619]

iex> Primacy.primes_near(600, count: 5, dir: :below)
[571, 577, 587, 593, 599]

iex> Primacy.primes_near(3, count: 5, dir: :below)
[2, 3]
```

`primes_near/2` options:

- `count`: how many primes to return (default: `1`)
- `dir`: `:below`, `:above`, or `:around` (default: `:around`)

Scanning downward stops at 2, so fewer than `count` primes may be returned.
A `count` of zero or less returns an empty list.

## Performance

`is_prime?/1` uses 6k ± 1 trial division below 4,000,000 and Miller-Rabin
above that, with deterministic witnesses below 2^64. A prime at or above
2^64 is confirmed by exhaustive trial division, which can take several
seconds. `primes_near/2` walks 6k ± 1 candidates instead of every integer.

Sample results on an Apple M5 from `mix bench`, comparing against the
plain trial-division baseline (labeled `old`):

| benchmark | trial division | Primacy |
|---|---|---|
| `is_prime?(123_456_794_333)` | 384 µs | 9.7 µs |
| `is_prime?(1_000_000_000_000_000_003)` | 10.8 s | 20 µs |
| `primes_near(1_000_000_000_000, count: 1_000)` | 1.8 s | 15 ms |

## Development

- `mix test` runs the test suite
- `mix test --include slow` adds the check for a prime above 2^64 (about 35 s)
- `mix bench` runs the benchee benchmark suite

## Documentation

Documentation can be generated with [ExDoc](https://github.com/elixir-lang/ex_doc)
and published on [HexDocs](https://hexdocs.pm). Once published, the docs can
be found at [https://hexdocs.pm/primacy](https://hexdocs.pm/primacy).