1. 素数（质数）

定义

大于1的自然数，除了1和它本身外没有其他因数。

示例

  • 判断一个数是否为素数
  • 打印某个范围内的所有素数
#include <stdio.h>
#include <math.h>

//判断n是否为素数 
int is_prime(int n){
    int i;
    for(i=2;i<=sqrt(n);i++){
        if(n%i==0){
            return 0;
        }
    }
    return 1;
}
//打印出a~b范围内的素数 
int print_prime_between(int a, int b){
    while(a<=b){
        if(is_prime(a)){
            printf("%d ", a);
        }
        a++;
    }
    printf("\n");
}

int main(){
    
    print_prime_between(2, 200);

    return 0;
}

变体

  • 孪生素数：相差2的素数对（如3和5、5和7）

    #include <stdio.h>
#include <math.h>

int is_prime(int n){
    int i;
    for(i=2;i<=sqrt(n);i++){
        if(n%i==0){
            return 0;
        }
    }
    return 1;
}

int main(){
    
    int i;
    for(i=2;i<1000;i++){
        if(is_prime(i) && is_prime(i+2)){
            printf("%d %d\n", i, i+2);
        }
    }

    return 0;
}

  • 梅森素数：形如 2^p-1 的素数（如3=2²-1，7=2³-1）

    #include <stdio.h>
#include <math.h>

int is_prime(int n){
    int i;
    for(i=2;i<=sqrt(n);i++){
        if(n%i==0){
            return 0;
        }
    }
    return 1;
}

int main(){
    
    int p=2;
    
    while(p < 10000){
        p*=2;
        if(is_prime(p-1)){
            printf("%d ", p-1);
        }
    }
    printf("\n");
    
    
    return 0;
}

  • 回文素数：既是素数又是回文数（如2, 3, 5, 7, 11, 101）

    #include <stdio.h>
#include <math.h>

int is_prime(int n){
    int i;
    for(i=2;i<=sqrt(n);i++){
        if(n%i==0){
            return 0;
        }
    }
    return 1;
}

int is_palindrome_number(int n){
    int t, s=0;
    t = n;
    while(t){
        s*=10;
        s+=t%10;
        t/=10;
    }
    return s == n; 
}

int main(){
    
    int i;
    for(i=2;i<1000;i++){
        if(is_prime(i) && is_palindrome_number(i)){
            printf("%d ", i);
        }
    }
    printf("\n");
    
    return 0;
}

2. 水仙花数（Narcissistic Number / Armstrong Number）

定义

n位数的各位数字的n次幂之和等于它本身 一位自幂数：独身数 三位自幂数：水仙花数 四位自幂数：四叶玫瑰数 五位自幂数：五角星数 六位自幂数：六合数 七位自幂数：北斗七星数 八位自幂数：八仙数 九位自幂数：九九重阳数 十位自幂数：十全十美数

示例

  • 153 = 1³ + 5³ + 3³
#include <stdio.h>

int main(){
    int i , a, b, c;
    
    for(i=100;i<1000;i++){
        a = i%10;
        b = i%100/10;
        c = i/100;
        
        if(a*a*a + b*b*b + c*c*c == i){
            printf("%d ", i);
        }
    }

    return 0;
}

变体

  • 阿姆斯特朗数（广义水仙花数）：可以是任意位数的水仙花数 1634 = 1⁴ + 6⁴ + 3⁴ + 4⁴

    #include <stdio.h>
#include <math.h>

int main(){
    int i, t, s, len;
    
    for(i=1;i<10000;i++){
        t = i;
        s=0;
        len = (int)log10(i)+1;
        while(t){
            s += pow(t%10, len);
            t/=10;
        }
        if(s == i){
            printf("%d ", i);
        }
    }


    return 0;
}

3. 回文数

定义

正读反读都相同的数字。

示例

  • 121, 1331, 12321

    #include <stdio.h>

int is_palindrome_number(int n){
    int t, s=0;
    t = n;
    while(t){
        s*=10;
        s+=t%10;
        t/=10;
    }
    return s == n; 
}


int main(){
    int i;
    for(i=1;i<100000;i++){
        if(is_palindrome_number(i)){
            printf("%d ", i);
        }
    }


    return 0;
}

变体

  • 回文平方数：如121 = 11²

    #include <stdio.h>

int is_palindrome_number(int n){
    int t, s=0;
    t = n;
    while(t){
        s*=10;
        s+=t%10;
        t/=10;
    }
    return s == n; 
}


int main(){
    int i;
    for(i=1;i<100000;i++){
        if(is_palindrome_number(i) && (int)sqrt(i) * (int)sqrt(i) == i){
            printf("%d ", i);
        }
    }


    return 0;
}

4. 完全数（完美数）

定义

等于其所有真因数（不包括自身的因数）之和的数。

示例

  • 6 = 1 + 2 + 3
  • 28 = 1 + 2 + 4 + 7 + 14
#include <stdio.h>

int main(){
    int i, j, s;
    for(i=1;i<10000;i++){
        s = 0;
        for(j=1;j<i;j++){
            if(i%j==0){
                s+=j;
            }
        }
        if(s == i){
            printf("%d ", i);
        }
    }
    printf("\n");

    return 0;
}

5. 完全平方数

定义

是某个整数的平方的数。

示例

  • 1 = 1²
  • 4 = 2²
  • 9 = 3²
#include <stdio.h>
#include <math.h>

int main(){

    int i;
    
    for(i=1;i<10000;i++){
        if((int)sqrt(i) * (int)sqrt(i) == i){
            printf("%d ", i);
        }
    }

    return 0;
}

6. 最大公约数（GCD）和最小公倍数（LCM）

最大公约数（GCD）

两个数的最大公共因数，如：

  • GCD(12, 18) = 6

最小公倍数（LCM）

两个数的最小公共倍数，如：

  • LCM(12, 18) = 36

关系

GCD(a,b)×LCM(a,b)=a×b

#include <stdio.h>

int gcd(int a, int b){
    int t;
    while(b){
        t =a%b;
        a = b;
        b = t;
    }
    return a;
}

int lcm(int a, int b){
    return a*b/gcd(a, b);
}

int main(){
    
    int a, b;
    
    scanf("%d %d", &a, &b);

    printf("最大公约数:%d\n", gcd(a, b));
    printf("最小公倍数:%d\n", lcm(a, b));

    return 0;
}

7. 分解质因数

定义

将一个合数分解为若干个质数的乘积。

示例

  • 12 = 2 × 2 × 3
  • 30 = 2 × 3 × 5
#include <stdio.h>

int main(){
    int n, i = 2;
    
    scanf("%d", &n);
    printf("%d=", n);
    while(i!=n){
        if(n%i==0){
            printf("%d*", i);
            n/=i;
            i--;
        }
        i++;
    }
    printf("%d\n", i);


    return 0;
}

8. 其他数字特性题目

(1) 亲密数（Amicable Numbers）

两个数中，一个数的所有真因数之和等于另一个数。

  • 示例：220 和 284
    • 220的真因数之和：1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284
    • 284的真因数之和：1 + 2 + 4 + 71 + 142 = 220
#include <stdio.h>

int factor(int n){
    int i, s = 0;
    for(i=1;i<n;i++){
        if(n%i==0){
            s+=i;
        }
    }
    return s;
}

int main(){
    int i;
    for(i=1;i<=10000;i++){
        if(factor(factor(i)) == i && factor(i) != i){
            printf("%d %d\n", i, factor(i));
            i=factor(i)+1;
        }
    }


    return 0;
}

(2) 阶乘数（Factorial Number）

等于某个数的阶乘。

  • 示例：1! = 1, 2! = 2, 3! = 6, 4! = 24
#include <stdio.h>

int factorial(int n){
    int i, s=1;
    for(i=2;i<=n;i++){
        s*=i;
    }
    
    return s;
}

int main(){
    int n;
    
    scanf("%d", &n);
    printf("%d\n", factorial(n));



    return 0;
}

(3) 斐波那契数（Fibonacci Number）

数列满足 F(0)=0,F(1)=1,F(n)=F(n−1)+F(n−2)F(0)=0,F(1)=1,F(n)=F(n−1)+F(n−2)。

  • 示例：0, 1, 1, 2, 3, 5, 8, 13, ...
#include <stdio.h>

int fib(int n){
    int i, a, b, t;
    a = b = 1;
    for(i=3;i<=n;i++){
        t = a + b;
        a = b;
        b = t;
    }
    
    return b;
}

int main(){
    int i;
    
    for(i=1;i<=20;i++){
        printf("%-5d", fib(i));
        if(i%5==0){
            printf("\n");
        }		
    }




    return 0;
}

(4) 组合数（Combination Number）

$$ C(n,k)= n!/ k!(n−k)! ​ $$

  • 示例：C(5,2)=10

组合数 C(n,k)（也称为 二项式系数）表示从 n个不同元素中选取 k 个元素的组合数。

#include <stdio.h>

int fact(int n){
    int i, s=1;
    for(i=2;i<=n;i++){
        s*=i;
    }
    
    return s;
}

int C(int n, int k){
    return fact(n)/(fact(k)*fact(n-k));
}

int main(){
    int n, k;
    
    scanf("%d %d", &n, &k);

    printf("C(%d, %d)=%d\n", n, k, C(n, k));

    return 0;
}

(5) 快乐数（Happy Number）

经过"各位平方和"运算最终变为1的数。

  • 示例：19 → 1² + 9² = 82 → 8² + 2² = 68 → 6² + 8² = 100 → 1² + 0² + 0² = 1（快乐数）
#include <stdio.h>

int sum_of_square(int n){
    int s=0;
    while(n){
        s+=(n%10)*(n%10);
        n/=10;
    }
    return s;
}

int is_happy(int n){
    int fast, slow;
    fast = slow = n;
    
    do{
        fast = sum_of_square(sum_of_square(fast));
        slow = sum_of_square(slow);
    }while(fast != slow);
    return fast == 1;
}

int main(){
    int i, s, t;
    
    for(i=19;i<200;i++){
        if(is_happy(i)){
            printf("%d ", i);
        }
    }
    printf("\n");


    return 0;
}

总结

类别 定义 示例
素数 大于1，只有1和自身两个因数 2, 3, 5, 7, 11
水仙花数 各位数字的n次方和等于自身 153, 370, 371
回文数 正读反读相同 121, 1331, 12321
完全数 真因数之和等于自身 6, 28, 496
完全平方数 是某个整数的平方 1, 4, 9, 16
GCD/LCM 最大公约数/最小公倍数 GCD(12,18)=6, LCM(12,18)=36
分解质因数 合数分解为质数乘积 12=2×2×3
亲密数 两个数的真因数之和互为对方 220 & 284
阶乘数 等于某个数的阶乘 1=1!, 2=2!, 6=3!
斐波那契数 F(n)=F(n-1)+F(n-2) 0,1,1,2,3,5,8
快乐数 平方和运算最终得1 19, 23, 28