问题：
- 2000以内的素数有哪些？
- 她的手机号是素数吗？
思路：
问题归类：
- 怎样获取n以内的所有素数呢？
- 怎样高效地判定一个正整数是否为素数呢？
假设已知：
第一个素数是2，第二个素数是3；
断定某正整数n确实为素数的依据是：当且仅当 若不超过n的算数平方根的所有素数都不能整除n，那么就断定n为素数。
酝酿策略：
先解决“获取n以内的所有素数”的问题，然后应用其结果来解决“高效地判定一个正整数是否为素数”的问题。
从第三个待定素数开始，以后总是把下一个候选素数的初始值取为当前已知的最后一个素数(必为奇数)；
然后执行下述循环
LOOP
EXIT WHEN 候选素数超过n；
把该待定素数(为奇数)的值更新为其下一个奇数的值：prime_number_candidate += 2;
探测该待定素数是否确实为素数：若是，则把它作为正式的素数写到素数数组中下一个素数的位置上；否则，直接去继续下一轮循环。
END LOOP
代码实践：
头文件：prime_number.h
1 #ifndef PRIME_NUMBER_H 2 #define PRIME_NUMBER_H 3 4 /*制定 素数数组的元素以及计数下标的数据类型*/ 5 typedef unsigned long long PRIME_INTEGER_TYPE, PRIME_INTEGER_ARRAY_COUNT_TYPE; 6 7 /*制定 容量可动态调整的素数数组容器数据类型*/ 8 typedef struct { 9 PRIME_INTEGER_TYPE *prime_integer_array; // 容量可动态调整的素数数组 10 PRIME_INTEGER_ARRAY_COUNT_TYPE count; // 素数数组中元素的数目 11 }PRIME_INTEGER_ARRAY_TYPE; 12 13 /************************************全局常量的声明************************************/ 14 extern const PRIME_INTEGER_ARRAY_TYPE EMPTY_PRIME_INTEGER_ARRAY; 15 extern const char *PRIME_INTEGER_TYPE_PRINT_FORMAT_STRING, *PRIME_INTEGER_ARRAY_COUNT_TYPE_PRINT_FORMAT_STRING; 16 17 /**************************************方法的声明**************************************/ 18 19 /*获取upper_limit以内的素数数组*/ 20 PRIME_INTEGER_ARRAY_TYPE getPrimeIntegerArrayBelow(PRIME_INTEGER_TYPE upper_limit); 21 22 /*格式化地打印upper_limit以内的全部素数*/ 23 void printPrimeIntegerArrayBelow(PRIME_INTEGER_TYPE upper_limit); 24 25 /*判断一个给定的数是否为素数*/ 26 int isPrimeInteger(PRIME_INTEGER_TYPE n); 27 28 #endif
源文件：prime_number.c
1 #include "prime_number.h" 2 #include <stdlib.h> 3 #include <stdio.h> 4 #include <math.h> 5 6 /************************************全局常量的定义************************************/ 7 const PRIME_INTEGER_ARRAY_TYPE EMPTY_PRIME_INTEGER_ARRAY = {NULL, 0}; // 空素数数组 8 const char *PRIME_INTEGER_TYPE_PRINT_FORMAT_STRING = "%2llu", *PRIME_INTEGER_ARRAY_COUNT_TYPE_PRINT_FORMAT_STRING = "%02llu"; // 设置打印素数数组时元素及下标的输出格式符 9 10 /**************************************方法的定义**************************************/ 11 12 /*获取素数探测者的上限*/ 13 PRIME_INTEGER_TYPE getProberUpperLimitFor(PRIME_INTEGER_TYPE prime_integer_candidate) { 14 /*取素数候选者的算术平方根的去尾近似值作为用来探测它是否确实为素数的素数探测者的上限*/
15 return llroundl(sqrtl(prime_integer_candidate*1.0));
16 } 17 18 /*获取upper_limit以内的素数数组*/ 19 PRIME_INTEGER_ARRAY_TYPE getPrimeIntegerArrayBelow(PRIME_INTEGER_TYPE upper_limit) { 20 /*最小的素数为2，因此在2之前的素数数组为空素数数组*/ 21 if (upper_limit < 2) { 22 return EMPTY_PRIME_INTEGER_ARRAY; 23 } 24 /*在upper_limit以内顶多有max_count个素数，*/ 25 PRIME_INTEGER_ARRAY_COUNT_TYPE max_count = (upper_limit + 1) / 2; 26 /*开辟足够的空间用来容纳upper_limit以内的全部素数*/ 27 PRIME_INTEGER_TYPE *prime_integer_array = (PRIME_INTEGER_TYPE *)malloc((size_t)(max_count) * sizeof(PRIME_INTEGER_TYPE)); 28 if (prime_integer_array == NULL) { 29 printf("Failed when doing malloc.\n"); 30 exit(1); 31 } 32 /*装载第一个素数*/ 33 prime_integer_array[0] = 2; 34 if (upper_limit == 2) { 35 return (PRIME_INTEGER_ARRAY_TYPE) { prime_integer_array, 1 }; 36 } 37 /*装载第二个素数*/ 38 prime_integer_array[1] = 3; 39 if (upper_limit <= 4) { 40 return (PRIME_INTEGER_ARRAY_TYPE) { prime_integer_array, 2 }; 41 } 42 /*后续素数均通过算法来