C++中的23种算法

核心提示：for(i = N - 1; i >=0; i--) {tmp = a[i] * b + carry;c[i] = tmp % 10000;carry = tmp / 10000;}}void div(int *a, int b, int *c) { // b 为除数int i, tmp, remain = 0;

for(i = N - 1; i >=0; i--) {

tmp = a[i] * b + carry;

c[i] = tmp % 10000;

carry = tmp / 10000;

}

}

void div(int *a, int b, int *c) { // b 为除数

int i, tmp, remain = 0;

for(i = 0; i < N; i++) {

tmp = a[i] + remain;

c[i] = tmp / b;

remain = (tmp % b) * 10000;

}

}

3.最大公因数、最小公倍数、因式分解

说明最大公因数使用辗转相除法来求，最小公倍数则由这个公式来求：

GCD*LCM=两数乘积

解法最大公因数可以使用递回与非递回求解，因式分解基本上就是使用小于输入数的数值当

作除数，去除以输入数值，如果可以整除就视为因数，要比较快的解法就是求出小于该数的所

有质数，并试试看是不是可以整除，求质数的问题是另一个课题，请参考Eratosthenes 筛选求

质数。

实作（最大公因数、最小公倍数）

#include <stdio.h>

#include <stdlib.h>

int main(void) {

int m, n, r;

int s;

printf("输入两数：");

scanf("%d %d", &m, &n);

s = m * n;

while(n != 0) {

r = m % n;

m = n;

n = r;

}

printf("GCD：%d\n", m);

printf("LCM：%d\n", s/m);

return 0;

}

实作（因式分解）

C（不用质数表）

#include <stdio.h>

#include <stdlib.h>

int main(void) {

int i, n;

printf("请输入整数：");

scanf("%d", &n);

printf("%d = ", n);

for(i = 2; i * i <= n;) {

if(n % i == 0) {

printf("%d * ", i);

n /= i;

}

else

i++;

}

printf("%d\n", n);

return 0;

}

C（使用质数表）

#include <stdio.h>

#include <stdlib.h>

#define N 1000

int prime(int*); // 求质数表

void factor(int*, int); // 求factor

int main(void) {

int ptable[N+1] = {0};

int count, i, temp;

count = prime(ptable);

printf("请输入一数：");

scanf("%d", &temp);

factor(ptable, temp);

printf("\n");

return 0;

}

int prime(int* pNum) {

int i, j;

int prime[N+1];

for(i = 2; i <= N; i++)

prime[i] = 1;

for(i = 2; i*i <= N; i++) {

if(prime[i] == 1) {

for(j = 2*i; j <= N; j++) {

if(j % i == 0)

prime[j] = 0;

}

}

}

for(i = 2, j = 0; i < N; i++) {

if(prime[i] == 1)

pNum[j++] = i;

}

return j;

}

void factor(int* table, int num) {

int i;

for(i = 0; table[i] * table[i] <= num;) {

if(num % table[i] == 0) {

printf("%d * ", table[i]);

num /= table[i];

}

else

i++;

}

printf("%d\n", num);

}

4.完美数

说明如果有一数n，其真因数（Proper factor）的总和等于n，则称之为完美数（Perfect Number），

例如以下几个数都是完美数：

6 = 1 + 2 + 3

28 = 1 + 2 + 4 + 7 + 14

496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248

程式基本上不难，第一眼看到时会想到使用回圈求出所有真因数，再进一步求因数和，不过若n