Trait IsPrime

pub trait IsPrime {
    // Required method
    fn is_prime(&self) -> bool;
}

A trait for testing whether a number is prime.

Required Methods

fn is_prime(&self) -> bool

Implementations on Foreign Types

impl IsPrime for u8

fn is_prime(&self) -> bool

Tests whether a u8 is prime.

This implementation just does a few divisibility checks.

If you want to generate many small primes, try using u8::primes instead.

Worst-case complexity

Constant time and additional memory.

Examples

use malachite_base::num::factorization::traits::IsPrime;

assert_eq!(5u8.is_prime(), true);
assert_eq!(6u8.is_prime(), false);

impl IsPrime for u16

fn is_prime(&self) -> bool

Tests whether a u16 is prime.

This implementation does a few divisibility checks, then performs strong probable prime tests with bases 31 and 73, which is enough to prove primality for any integer less than $2^{16}$.

If you want to generate many small primes, try using u16::primes instead.

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Examples

use malachite_base::num::factorization::traits::IsPrime;

assert_eq!(5u16.is_prime(), true);
assert_eq!(6u16.is_prime(), false);
assert_eq!(65521u16.is_prime(), true);

impl IsPrime for u32

fn is_prime(&self) -> bool

Tests whether a u32 is prime.

This implementation does a few divisibility checks, then performs a few strong probable prime tests, which is enough to prove primality for any integer less than $2^{32}$.

If you want to generate many small primes, try using u32::primes instead.

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Examples

use malachite_base::num::factorization::traits::IsPrime;

assert_eq!(5u32.is_prime(), true);
assert_eq!(6u32.is_prime(), false);
assert_eq!(4294967291u32.is_prime(), true);

impl IsPrime for u64

fn is_prime(&self) -> bool

Tests whether a u64 is prime.

This implementation first does a few divisibility checks. Then, depending on the input, it either runs a few strong probable prime tests or the Baillie–PSW test. This is enough to prove primality for any integer less than $2^{64}$.

If you want to generate many small primes, try using u64::primes instead.

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Examples

use malachite_base::num::factorization::traits::IsPrime;

assert_eq!(5u64.is_prime(), true);
assert_eq!(6u64.is_prime(), false);
assert_eq!(5509785649208481923u64.is_prime(), true);

impl IsPrime for usize

fn is_prime(&self) -> bool

Tests whether a usize is prime.

This implementation first does a few divisibility checks. Then, depending on the input, it either runs a few strong probable prime tests or the Baillie–PSW test. This is enough to prove primality for any integer that fits in a usize.

If you want to generate many small primes, try using usize::primes instead.

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Examples

use malachite_base::num::factorization::traits::IsPrime;

assert_eq!(5usize.is_prime(), true);
assert_eq!(6usize.is_prime(), false);
assert_eq!(4294967291usize.is_prime(), true);

Implementors