malachite_base/num/arithmetic/
coprime_with.rs

1// Copyright © 2025 Mikhail Hogrefe
2//
3// This file is part of Malachite.
4//
5// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
6// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
7// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.
8
9use crate::num::arithmetic::traits::CoprimeWith;
10use crate::num::basic::unsigneds::PrimitiveUnsigned;
11
12pub_test! {coprime_with_check_2<T: PrimitiveUnsigned>(x: T, y: T) -> bool {
13    (x.odd() || y.odd()) && x.gcd(y) == T::ONE
14}}
15
16#[cfg(feature = "test_build")]
17pub fn coprime_with_check_2_3<T: PrimitiveUnsigned>(x: T, y: T) -> bool {
18    (x.odd() || y.odd())
19        && (!x.divisible_by(T::from(3u8)) || !y.divisible_by(T::from(3u8)))
20        && x.gcd(y) == T::ONE
21}
22
23#[cfg(feature = "test_build")]
24pub fn coprime_with_check_2_3_5<T: PrimitiveUnsigned>(x: T, y: T) -> bool {
25    if x.even() && y.even() {
26        false
27    } else {
28        let c15 = T::from(15u8);
29        let c3 = T::from(3u8);
30        let c6 = T::from(6u8);
31        let c9 = T::from(9u8);
32        let c12 = T::from(12u8);
33        let c5 = T::from(5u8);
34        let c10 = T::from(10u8);
35        let x15 = x % c15;
36        let y15 = y % c15;
37        if (x15 == T::ZERO || x15 == c3 || x15 == c6 || x15 == c9 || x15 == c12)
38            && (y15 == T::ZERO || y15 == c3 || y15 == c6 || y15 == c9 || y15 == c12)
39        {
40            return false;
41        }
42        if (x15 == T::ZERO || x15 == c5 || x15 == c10)
43            && (y15 == T::ZERO || y15 == c5 || y15 == c10)
44        {
45            return false;
46        }
47        x.gcd(y) == T::ONE
48    }
49}
50
51macro_rules! impl_coprime_with {
52    ($t:ident) => {
53        impl CoprimeWith<$t> for $t {
54            /// Returns whether two numbers are coprime; that is, whether they have no common factor
55            /// other than 1.
56            ///
57            /// Every number is coprime with 1. No number is coprime with 0, except 1.
58            ///
59            /// $f(x, y) = (\gcd(x, y) = 1)$.
60            ///
61            /// $f(x, y) = ((k,m,n \in \N \land x=km \land y=kn) \implies k=1)$.
62            ///
63            /// # Worst-case complexity
64            /// $T(n) = O(n^2)$
65            ///
66            /// $M(n) = O(n)$
67            ///
68            /// where $T$ is time, $M$ is additional memory, and $n$ is
69            /// `max(self.significant_bits(), other.significant_bits())`.
70            ///
71            /// # Examples
72            /// See [here](super::coprime_with#coprime_with).
73            #[inline]
74            fn coprime_with(self, other: $t) -> bool {
75                coprime_with_check_2(self, other)
76            }
77        }
78    };
79}
80apply_to_unsigneds!(impl_coprime_with);
malachite_base/num/arithmetic/coprime_with.rs

malachite_base/num/arithmetic/
coprime_with.rs
