C语言-输出指定个数的质数

质数概念

只能被 1 和自身整除的对于 1 正整数。

2, 3, 5, 7, ...

指针声明和初始化

unsigned long long *pPrimes = NULL;

NULL 对指针而言相当于 0 值,在声明指针的时候最好将其初始化为 NULL 防止其乱指,在后面使用过程中

造成内存覆盖等问题。

声明需要的变量:

1
2
3
4
5
6
// 用来存储所有的质数
unsigned long long *pPrimes = NULL;
unsigned long long trial = 0;
_Bool found = false;
int total = 0; // 需要输出的总质数个数
int count = 0; // 用来计数

pPrimes 指针用来存放动态分配的内存首地址。
trial 用来获得当前将要被处理的可能是质数的数。
total 用户需要展示的质数的个数,由用户输入。
count 循环的计数。

动态分配内存(malloc() 或 calloc())

malloc()calloc() 区别在于 calloc() 有两大有点:

  1. 将内存分配为给定大小的数组;
  2. 会将所有分配的内存初始化为 0

因此尽量使用 calloc 去动态分配内存。

这里我们固定内存的容量大小为: size_t capacity = 10; 使用 size_t 是因为

calloc()malloc() 的第二个参数类型为 size_t 类型。

1
2
3
4
5
6
7
8
9
10
11
printf("请问想要输出多少个质数(至少4个) ? ");
scanf("%d", &total);

// 根据输入个数分配空间
// 固定初次分配的内存量
size_t capacity = 10;
pPrimes = (unsigned long long *)calloc(capacity, sizeof(unsigned long long));
if (!pPrimes) {
printf("内存分配失败。");
return 1;
}

记得分配完内存在使用之前,一定要做非空判断,判断是否分配成功,只有成功了才能继续往下,否则可能会造成未知的严重后果。

获取已知的质数

根据质数的特性,我们先声明几个已知的质数(2, 3, 5),然后根据这些已知的质数,去被将来的质数整除,只要能整除,说明

它不是质数。

1
2
3
4
5
6
// 直接找出前 3 个质数 (2, 3, 5)
*pPrimes = 2ULL;
*(pPrimes + 1) = 3ULL;
*(pPrimes + 2) = 5ULL;
count = 3;
trial = 5ULL;

通过下面的循环去找出下一个质数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
unsigned long long *pTemp = NULL;
while (count < total) {
trial += 2ULL; // 直接跳过偶数

// 计算是否能被现有的质数整除,如果能表示非质数
// 这里使用 i = 1 是因为 任何奇数都无法被2整除,
// 因此没必要对 2 进行判断
for (int i = 1; i < count; i++) {
if (!(found = (trial % *(pPrimes + i))))
break;
}

if (found) {
*(pPrimes + count++) = trial;
}
}

trail += 2ULL; 这里使用了个技巧,因为我们知道除了 2 意外的偶数(>0)都不会是质数,因此偶数就没必要

去做多余的判断了。

经过上面的 while 循环我们将找到下一个质数:

*(pPrimes + count++) = trial;

并将它放到最后一个质数的后面通过 *(pPrimes + count++) ,因为指针的 +1 是根据其指针存放的数据类型

的大小递增的,因此可以直接通过指针 +count 来找到要存放当前质数的地址。

但前提是最后一个质数空间后面有更多的空间去容纳它,那么这个时候就需要考虑去动态分配更多的空间了,

因为我们最初只固定分配了 CAP_INCR 个内存空间。

再分配内存(realloc())

realloc() 会在 malloc()calloc() 基础之上分配更多的内存空间,并且会将旧的内存拷贝到新的内存中。

比如:

malloc()5 个内存空间:

1 2 3 4 5

然后通过 realloc() 分配 10 个内存空间:

0 0 0 0 0 0 0 0 0 0

然后会把 malloc() 分配的内存里的内容拷贝到新的里面成为:

1 2 3 4 5 0 0 0 0 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 是否找到 ??
if (found) {
// 找到之后得先判断内存是否够用,不够用需要再分配
if (count == capacity) {
capacity += CAP_INCR;
pTemp = realloc(pPrimes, capacity * sizeof(unsigned long long));
if (!pTemp) {
printf("realloc failed.\n");
free(pPrimes);
pPrimes = NULL;
return 2;
}
pPrimes = pTemp;
}
// 将找到的质数保存起来
*(pPrimes + count++) = trial;
}

上面声明了一个新的指针 pTemp 用来指向再分配的内存空间,但是会发现我们后面并没有去针对这个指针去做释放操作,

这是因为我们后面将 pPrimes 指向了 pTemp ,而我们也在后面对 pPrimes 进行了释放。

即如果两个指针同时指向一个内存空间的话,只需要释放一个就可以了,如果两个都去调用 free() 进行释放,

其实就是意味着对同一块内存进行两次释放,这个也可能会造成不可预知的问题,因此切记不要对同一块内存进行两次甚至

更多次的释放操作。

输出结果并释放内存,置空指针

1
2
3
4
5
6
7
8
9
10
11
12
13
// 输出得到的质数
for (int i = 0; i < total; i++) {
printf("%12llu", *(pPrimes + i));
if (!((i + 1) % 5)) { // 被 5 整除换行,一行显示5个
printf("\n");
}
}
printf("\n");

// 释放内存
free(pPrimes);
// 置空指针
pPrimes = NULL;

分配内存之后,不用的时候不单单要调用 free() 去释放,释放之后,这个指针也需要置空处理,防止乱指。

完整代码

总结

该实例完成,主要是认识 malloc(), calloc()realloc() 动态分配内存以及内存释放函数的使用,及其相关的一些知识和注意点和质数的概念。

本文标题:C语言-输出指定个数的质数

文章作者:ZhiCheng Lee

发布时间:2019年04月22日 - 16:01:45

最后更新:2019年04月22日 - 16:01:45

原始链接:http://blog.gcl666.com/2019/04/22/c_alloc_primes/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%