C 关于素数的两道题和相关算法

这道题目有点意思。

1.如果一个数是素数，则指出是素数，否则写出因数。
2.输入一个整数，显示所有小于等于该数的素数。

首先明确什么是素数再说，实际上概念我忘得差不多了：

質數，又称素数，指在大於1的自然数中，除了1和此整数自身外，無法被其他自然数整除的数（也可定義為只有1和本身两个因数的数）。

先看看第一题的源码：

#include <stdio.h>
#include <stdbool.h>

int main(void)
{
    unsigned long num;
    unsigned long div;
    bool isPrime;

    printf("Please enter an integer for analysis: ");
    printf("Enter q to quit.\n");
    while (scanf("%lu", &num) == 1) {
        for (div = 2, isPrime = true; (div * div) <= num; div++) {
            if (num % div == 0) {
                if ((div * div) != num)
                    printf("%lu is divisible by %lu and %lu.\n", num, div, num / div);
                else
                    printf("%lu is divisible by %lu.\n", num, div);
                isPrime = false;
            }
        }
        if (isPrime)
            printf("%lu is prime.\n", num);
        printf("Please enter another integer for analysis: ");
        printf("Enter q to quit.\n");
    }
    printf("Bye.\n");
    return 0;
}

这里用到了几个新知识，第一是<stdbool.h>引出bool（否则的话在C99也是能用_Bool的）但是平时没有必要，因为布尔型在日常应用中几乎没有人会特地使用。然后我们就能用true和false了。

然后再来看一个有意思的：(div * div) <= num
这里这么定义可能会有点不理解，但实际上，可以看作把num开根号了，换句话说就是对半开，因为公约数其实是对称情况，这一点我们可以看看，输入144：

144 is divisible by 2 and 72.
144 is divisible by 3 and 48.
144 is divisible by 4 and 36.
144 is divisible by 6 and 24.
144 is divisible by 8 and 18.
144 is divisible by 9 and 16.
144 is divisible by 12.

所以我们只要运算到一半（开根）就行了，这样执行效率快了一倍（这就是效率问题了）另外if ((div * div) != num)使得相同的公约数不会重复输出。

scanf("%lu", &num) == 1在以前曾经介绍过：C 一个程序说说scanf()判断如果数值类型不对应，它是无法成功读取的，如果是%d 而输入则是123A那么在A处会停止。

那么第二道题其实类似，只是加了一层嵌套而已。

/* Programmming Exercise 7-9 */
#include <stdio.h>
#define NO 0
#define YES 1
int main(void)
{
   long num;                      /* value to be checked */
   long div;                      /* potential divisors  */
   long lim;                      /* limit to values     */
   int prime;

   printf("Please enter limit to values to be checked; ");
   printf("Enter q to quit.\n");
   while (scanf("%ld", &lim) == 1 && lim > 0)
   {
         for (num = 2; num <= lim; num++)
         {
          for (div = 2, prime = YES; (div * div) <= num; div++)
             if (num % div == 0)
                prime = NO;           /* number is not prime  */
          if (prime == YES)
             printf("%ld is prime.\n", num);
      }
      printf("Please enter another limit; ");
      printf("Enter q to quit.\n");
   }
   return 0;
}