计算机程序的构造和解释 1.21 寻找素数因子

寻找素数因子

要求用书中的smallest-divisor过程找出199, 1999, 19999的最小因子。

Scheme Code：

主要流程：

定义寻找素数的过程

如果2的平方即4，大于测试值，那么它肯定是素数

如果n能和2整除，那么不是素数，最小因子是2

如果不是，回到过程find-div，再试试能不能与2+1整除，循环

 

#lang racket
(define (square x)
  (* x x))
;定义筛选
(define (smallest-div n)
  (find-div n 2))

(define (find-div n td)
  (cond ((> (square td) n) n)
        ((divd? td n) td)
        (else (find-div n (+ td 1)))))
 
(define (divd? a b)
  (= (remainder b a) 0))
;primer过程，如果满足条件那么等于true,否则false，用#t和#f表示，类似bool
(define (primer? n)
  (= n (smallest-div n)))

 

测试：

 

IN：

 

(primer? 3)

 

(smallest-div 199)

 

(smallest-div 1999)

 

(smallest-div 19999)

 

OUT：

 

#t

 

199

 

1999

 

7

C++ Code：

 

int square(int x){
    int sum = x*x;
    return sum;
}
int find_div(int n,int td){
    if (square(td)>n)
    {
       return n;
    }
    else if (!(n%td))
    {
       return td;
    }
    else
    {
       find_div(n, td + 1);
    }
}
int _tmain(int argc, _TCHAR* argv[])
{
    int a, b,real;
    cin >> a >> b;
    real = find_div(a, b);
    cout << real << endl;
    return 0;
}