intmain() { int n, i = 2, flag = 0, raw_n; scanf("%d", &n); raw_n = n; // 循环终止条件,循环到 n 的平方根结束 while (i * i <= n) { //①:只要 n 可以被 i 整除,就认为 i 是 n 的一个素因子 while (n % i == 0) { print_num(i, &flag); n /= i; } i += 1; } //②:如果最后 n 不等于 1,就说明 n 是最后一个素数 if (n != 1) print_num(n, &flag); printf(" = %d\n", raw_n); return0; }
试证明:
1,第 18 行代码中,只要 n 可以被 i 整除,i 就一定是素数,为什么? 假设 i 可以被 n 整除,但 i 不是素数,由算术基本定理可知,一个非素数的数字 N,一定可以分解为几个小于 N 的素数乘积的形式。我们不妨假设 i=p1×p2,这里 p1 和 p2 均为素数,如果变量 n 可以被 i 整除,那么 n 也一定可以被小于 i 的素数 p1 整除。而根据程序的运行流程,n 中已经不可能存在小于 i 的因子了,所以 p1 不具备存在的条件,故原假设不成立,i 是素数。
2,第 25 行代码中,为什么只要 n 不等于 1,n 就一定是素数呢? 在 while 循环处理过程中,数字 n 中已经不可能存在小于等于 i 的所有的因子了,又因为此时 i 是大于根号 n 的一个值,也就是说,在小于等于根号 n 范围内,找不到数字 n 的非 1 因子,而能够满足这种性质的数字,一定是素数。