爱来自ZZULI❤drluo

第一题

编写一个C语言函数（isPrime），该函数接受一个整数作为参数，检查该整数是否为质数（只能被1和自身整除的数），然后返回一个布尔值，如果是质数则返回1，否则返回0

注意：

请使用long long 代替 int，因为用于测试的数字可能很大（抱歉，后续测试数据依旧选择在了21亿范围内，即int类型范围，相关使用long long进行编写的代码，在测试时，一律手动修改为int，以确保不会因为类型影响计算速度）

（相关函数类型为bool的，也进行了调整，测试时保证所有人的函数均为int类型，传递的参数，内部参数均为int类型）

你的函数应该只有一个参数，并返回一个整数（1或0），用于表示是否为质数，并且不使用其他外部库或函数来进行质数检查(后经考虑，此函数允许使用sqrt（开方相较于乘积，为耗时操作）)。

最终，你的函数将通过这样的方式被调用：

1
2
3
4
5
6
if (isPrime(num)) {
	printf("%d 是质数\n", num);
}
else {
	printf("%d 不是质数\n", num);
}

其中：isPrime是判断num是否为质数的函数

此题采用了时间评分，具体代码已在文件中给出。时间评分代码不做解读。

有同学使用sqrt函数，其实完全可以用i * i <= n平替

有的同学将sqrt置于循环判断条件中，导致sqrt被频繁调用，开方被频繁计算，耗时较大。

for(int i=2; i <= sqrt(n); i++);

可以优化为：

int k = sqrt(n);

for(int i=2; i <= k; i++);

或者采用上方i * i <= n 的形式，乘积操作的耗时远小于开方。

下方代码思路仅作参考

75分代码思路（时间分0）

此分段核心思路在于：

使用一个循环从2开始，逐个检查所有大于等于2且小于n的整数是否能整除n，如果能整除，表明n不是质数，返回0。

1
2
3
4
5
6
7
8
9
10
11
12
int isPrime(int n) {
    if (n <= 1) {
        return 0; // 1不是质数
    }
    for (int i = 2; i < n; i++) {
        if (n % i == 0) {
            return 0; // 如果能被某个整数整除，不是质数
        }
    }
    return 1; // 是质数

}

85 - 87分代码思路（时间分0.4~0.48）

此分段核心思路在于：

使用一个循环从2开始，逐个检查所有大于等于2且小于等于n的平方根的整数是否能整除n，如果能整除，表明n不是质数，返回0。

判断重点必须包含等于，比如这个，它是由一个质数的平方组成：

90193009

它不是质数

9497*9497 = 90193009

如果循环停止条件是i * i < n

那么最多会判断到9496，然后就会结束循环，从而忽略掉这个数是由质数相乘组成的条件。

采用检查到n的平方根的操作，极大的减少了循环时间。这是因为大于sqrt(n)的因子一定无法整除n

1
2
3
4
5
6
7
8
9
10
11
12
int isPrime(int n) {
    if (n <= 1) {
        return 0; // 1不是质数
    }
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return 0; // 如果能被某个整数整除，不是质数
        }
    }
    return 1; // 是质数

}

92 - 94分代码思路（时间分0.72~0.76）

此分段核心思路在于：

使用一个循环从5开始，逐个检查大于等于5且小于等于n的平方根的奇数（5，7，9，11，13，15，…）是否能整除n，如果能整除，表明n不是质数。

这个循环只检查奇数因子，跳过了偶数因子，从而提高了效率

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int isPrime(int n) {
    if (n <= 1) {
        return 0; // 1不是质数
    }
    if (n <= 3) {
        return 1; // 2和3是质数
    }
    if (n % 2 == 0 || n % 3 == 0) {
        return 0; // 如果能被2或3整除，不是质数
    }
    for (int i = 5; i * i <= n; i += 2) {
        if (n % i == 0) {
            return 0;
        }
    }
    return 1;
}

95 - 96分代码思路（时间分0.8 ~ 0.84）

此分段：

核心思路与92 - 94分相似，相较于前一种代码循环步进i += 2的方式，该代码循环步进的方式为 i += 6，然后检查6的倍数附近的两个数if (n % i == 0 || n % (i + 2) == 0)作为可能的因子。

为什么要检查n % i 和 n % (i + 2)，而不是n % i 和 n % (i + 3) ，n % i 和n % (i + 5) 这样的呢？

因为如果 n 是一个质数（不为2或3）那么 n % 2 != 0 且 n % 3 != 0这是肯定的

这两个语句可以解释为：

由于 n 不能被2或3整除，如果n是一个质数，那么它的只可能是：6k ± 1的形式，其中 k 是一个整数。

让我们判断一下6k附近的数（6k，6k + 1，6k + 2，6k + 3，6k + 4，6k + 5…）有哪些特点：

其中，6k， 6k + 2，6k + 3，6k + 4 都可以被2整除，这些数不是质数

所以我们只需要判断6k + 1和6k + 5是否为质数即可。（6k + 1 和6k + 5 可以看成： 6w + 1 和 6w - 1 可以理解成6k两侧的数）

我们的循环中 for (int i = 6; i * i <= n; i += 6)

i 从6开始，每次自增6

所以对于我们推导出的规律：判断6k + 1和6k + 5是否为质数

在我们这个从6开始的循环中表示为：n能否被i - 1和i + 1整除（即为：n能否被6k - 1和6k + 1整除）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int isPrime(int n) {
    if (n <= 1) {
        return 0; // 1不是质数
    }
    if (n <= 3) {
        return 1; // 2和3是质数
    }
    if (n % 2 == 0 || n % 3 == 0) {
        return 0; // 如果能被2或3整除，不是质数
    }
    for (int i = 6; i * i <= n; i += 6) {
        if (n % (i - 1) == 0 || n % (i + 1) == 0) {
            return 0;
        }
    }
    return 1;
}

99-100分代码思路（时间分0.96 ~ 1）【思路1属于牺牲空间换取时间，思路2看看即可】

思路1（牺牲空间换取时间）

额外编写一个函数：

//存储数字是否为质数

//获取完质数表后，判断某数是否为质数，只需采用：if(isprime[num])的形式。

bool isprime[MAX];

void getprime(int listsize);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool isprime[MAX];

void getprime(int listsize) {
    memset(isprime, 1, sizeof(isprime));
    isprime[1] = false;
    primesize = 0;

    for (int i = 2; i <= MAX && i <= listsize; i++) {
        if (isprime[i])prime[++primesize] = i;
        for (int j = 1; j <= primesize && i * prime[j] < listsize; j++) {
            isprime[i * prime[j]] = false;
            if (i % prime[j] == 0)break;
        }
    }
    isprime[0] = 0;
}

int isPrime(int num) {
    return isprime[num];
}

思路2 （Miller-Rabin素数测试）

这是一种概率性的质数测试方法，通常用于确定一个数是否很可能是质数。

这个方法比起传统的除法检查要更快，尤其适合大数。

但是这是一种概率性判断，它的结果不一定准确。

有兴趣可以去看【朝夕的ACM笔记】数论-Miller Rabin素数判定 - 知乎 (zhihu.com)

下面是一个该算法的例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
// 快速幂取模算法
long long fastModuloExponentiation(long long base, long long exponent, long long modulo) {
    long long result = 1;
    base %= modulo;
    while (exponent > 0) {
        if (exponent % 2 == 1) {
            result = (result * base) % modulo;
        }
        exponent >>= 1;
        base = (base * base) % modulo;
    }
    return result;
}

bool millerRabinTest(long long n) {
    int k = 4;//进行Miller-Rabin测试的迭代次数,k的值越大，测试越可靠
    if (n <= 1) {
        return false;
    }
    if (n <= 3) {
        return true;
    }
    if (n % 2 == 0) {
        return false;
    }

    long long d = n - 1;//n此时确定为奇数，n-1为偶数
    while (d % 2 == 0) {
        d /= 2; // 计算 d，使 n - 1 可写为 2^r * d（2的r次方乘d的形式），其中 d 为奇数
    }

    for (int i = 0; i < k; i++) {
        long long a = 2 + rand() % (n - 3); // 随机选择基数 a，其中 2 <= a <= n - 2

        // 使用快速幂取模算法计算 a^d % n
        long long x = fastModuloExponentiation(a, d, n);

        if (x == 1 || x == n - 1) {
            continue;
        }

        while (d != n - 1) {
            x = (x * x) % n;
            d *= 2;

            if (x == 1) {
                return false;
            }
            if (x == n - 1) {
                break;
            }
        }

        if (x != n - 1) {
            return false;
        }
    }

    return true; // 通过 k 次测试后，n 可能是质数
}



//通过isPrime跳转，方便测试函数调用。
int isPrime(int num) {
    return millerRabinTest(num);
}

第二题

分别编写一个或两个C语言函数，用于查找数组中的最大值和最小值，你的函数应该包含一个整数数组，数组的大小作为参数,你可以另外添加参数，此题不进行时间评分。

如果你选择编写两个函数：

  • 不可以使用全局变量。

  • 第一个函数的可以返回数组中的最大值。

  • 第二个函数可以返回数组中的最小值。

  • 不可以引用除stdio.h之外的头文件库。

  • 若使用排序，排序函数应手动实现。

如果你选择编写一个函数：

  • 不可以使用全局变量。

  • 该函数应该通过某种方式返回最大值和最小值，可以使用一个或多个变量。

  • 可以使用结构体（不使用结构体依旧可以实现）。

  • 不可以引用除stdio.h之外的头文件库。

  • 若使用排序，排序函数应手动实现。

以下四种思路均可得分

思路一（两个函数）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<stdio.h>
int getMax(int arr[], int sz) {
    int max = arr[0];
    for (int i = 1; i < sz; i++) {
        if (max < arr[i]) {
            max = arr[i];
        }
    }
    return max;
}

int getMin(int arr[], int sz) {
    int min = arr[0];
    for (int i = 1; i < sz; i++) {
        if (min > arr[i]) {
            min = arr[i];
        }
    }
    return min;
}
int main()
{
    int b, c;
    int arr[] = { 1,2,3,4,5,-1,-2,-3,-4,-5 };
    int sz = sizeof arr / sizeof arr[0];
    printf("最大值为%d\n", getMax(arr, sz));
    printf("最小值为%d\n", getMin(arr, sz));
    return 0;
}

思路二(一个函数，指针实现)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <stdio.h>

void findMinMax(int arr[], int size, int* min, int* max) {
    *min = *max = arr[0];

    for (int i = 1; i < size; i++) {
        if (arr[i] > *max) {
            *max = arr[i];
        }
        if (arr[i] < *min) {
            *min = arr[i];
        }
    }
}

int main() {
    int array[] = { 7,89,76,-34,-9,123,26,421,124,87,7 };
    int size = sizeof(array) / sizeof(array[0]);
    int minValue, maxValue;

    findMinMax(array, size, &minValue, &maxValue);

    printf("最小值为: %d\n", minValue);
    printf("最大值为: %d\n", maxValue);

    return 0;
}

思路三 （一个函数，结构体实现）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<stdio.h>

typedef struct VALUE{
	int max;
	int min;
}VALUE;

VALUE findMinMax(int arr[], int sz)
{
    VALUE value = { 0,0 };
    for (int i = 1; i < sz; i++) {
        if (arr[i] > value.max) {
            value.max = arr[i];
        }
        if (arr[i] < value.min) {
            value.min = arr[i];
        }
    }
    return value;
}


int main()
{
	int arr[] = { 7,89,76,-34,123,26,421,124,87,7 };
	int sz = sizeof(arr) / sizeof(arr[0]);

    VALUE value = findMinMax(arr, sz);
    printf("最大值为%d\n", value.max);
    printf("最小值为%d\n", value.min);
    return 0;
}

思路四（一个函数，排序实现）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<stdio.h>
void _sort(int arr[], int sz)
{
	int temp = 0;
	for (int i = 0; i < sz; i++) {
		for (int j = i + 1; j < sz; j++) {
			if (arr[i] > arr[j]) {
				temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		}
	}
}


int main()
{
	int arr[] = { 7,89,76,-34,123,26,421,124,87,7 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	_sort(arr, sz);

    printf("最大值为%d\n", arr[sz - 1]);
    printf("最小值为%d\n", arr[0]);
    return 0;
}