Trait malachite_base::num::arithmetic::traits::CoprimeWith

pub trait CoprimeWith<RHS = Self> {
    // Required method
    fn coprime_with(self, other: RHS) -> bool;
}

Determines whether two numbers are coprime.

Required Methods

fn coprime_with(self, other: RHS) -> bool

Implementations on Foreign Types

impl CoprimeWith for u8

fn coprime_with(self, other: u8) -> bool

Returns whether two numbers are coprime; that is, whether they have no common factor other than 1.

Every number is coprime with 1. No number is coprime with 0, except 1.

$f(x, y) = (\gcd(x, y) = 1)$.

$f(x, y) = ((k,m,n \in \N \land x=km \land y=kn) \implies k=1)$.

Worst-case complexity

$T(n) = O(n^2)$

$M(n) = O(n)$

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

Examples

See here.

impl CoprimeWith for u16

fn coprime_with(self, other: u16) -> bool

Returns whether two numbers are coprime; that is, whether they have no common factor other than 1.

Every number is coprime with 1. No number is coprime with 0, except 1.

$f(x, y) = (\gcd(x, y) = 1)$.

$f(x, y) = ((k,m,n \in \N \land x=km \land y=kn) \implies k=1)$.

Worst-case complexity

$T(n) = O(n^2)$

$M(n) = O(n)$

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

Examples

See here.

impl CoprimeWith for u32

fn coprime_with(self, other: u32) -> bool

Returns whether two numbers are coprime; that is, whether they have no common factor other than 1.

Every number is coprime with 1. No number is coprime with 0, except 1.

$f(x, y) = (\gcd(x, y) = 1)$.

$f(x, y) = ((k,m,n \in \N \land x=km \land y=kn) \implies k=1)$.

Worst-case complexity

$T(n) = O(n^2)$

$M(n) = O(n)$

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

Examples

See here.

impl CoprimeWith for u64

fn coprime_with(self, other: u64) -> bool

Returns whether two numbers are coprime; that is, whether they have no common factor other than 1.

Every number is coprime with 1. No number is coprime with 0, except 1.

$f(x, y) = (\gcd(x, y) = 1)$.

$f(x, y) = ((k,m,n \in \N \land x=km \land y=kn) \implies k=1)$.

Worst-case complexity

$T(n) = O(n^2)$

$M(n) = O(n)$

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

Examples

See here.

impl CoprimeWith for u128

fn coprime_with(self, other: u128) -> bool

Returns whether two numbers are coprime; that is, whether they have no common factor other than 1.

Every number is coprime with 1. No number is coprime with 0, except 1.

$f(x, y) = (\gcd(x, y) = 1)$.

$f(x, y) = ((k,m,n \in \N \land x=km \land y=kn) \implies k=1)$.

Worst-case complexity

$T(n) = O(n^2)$

$M(n) = O(n)$

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

Examples

See here.

impl CoprimeWith for usize

fn coprime_with(self, other: usize) -> bool

Returns whether two numbers are coprime; that is, whether they have no common factor other than 1.

Every number is coprime with 1. No number is coprime with 0, except 1.

$f(x, y) = (\gcd(x, y) = 1)$.

$f(x, y) = ((k,m,n \in \N \land x=km \land y=kn) \implies k=1)$.

Worst-case complexity

$T(n) = O(n^2)$

$M(n) = O(n)$

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

Examples

See here.

Implementors