Module: CodeCook::NumberTheory

Defined in:
手写代码必备手册(Ruby版).rb

Overview

第十五章

Class Method Summary (collapse)

Class Method Details

+ (Integer) gcd(a, b)

辗转相除法

求最大公约数,欧几里德算法

Parameters:

  • a (Integer)
  • b (Integer)

Returns:

  • (Integer) —

    a和b的最大公约数



701
702
703
704
 
# File '手写代码必备手册(Ruby版).rb', line 701

def gcd(a, b)
    return a if b == 0
    gcd(b, a%b)
end

+ (Integer) gcd1(a, b)

迭代版本

求最大公约数,欧几里德算法

Parameters:

  • a (Integer)
  • b (Integer)

Returns:

  • (Integer) —

    a和b的最大公约数



712
713
714
715
716
717
718
719
 
# File '手写代码必备手册(Ruby版).rb', line 712

def gcd1(a, b)
    while b != 0
        c = b
        b = a % b
        a = c
    end
    a
end

+ (Integer) gcd2(a, b)

迭代版本,基于减法

求最大公约数,欧几里德算法

Parameters:

  • a (Integer)
  • b (Integer)

Returns:

  • (Integer) —

    a和b的最大公约数



727
728
729
730
731
732
733
734
735
736
 
# File '手写代码必备手册(Ruby版).rb', line 727

def gcd2(a, b)
    while a != b
        if a > b
            a -= b
        else
            b -= a
        end
    end
    a
end

+ (Integer) is_prime(n)

15.1.3 素数判定

Parameters:

  • n (Integer) —

    被判断是否为素数的数字

Returns:

  • (Integer) —

    0表示不是素数，1表示是素数



742
743
744
745
746
747
748
749
750
 
# File '手写代码必备手册(Ruby版).rb', line 742

def is_prime(n)
    return 0 if n < 2
    i = 2
    while i*i <= n
        return 0 if n % i == 0
        i += 1
    end
    return 1
end