c语言入一个正整数，判断此数是否为质数

<think>我们使用C语言编写一个程序来判断一个正整数是否为质数（素数）。素数的定义是：大于1的自然数中，除了1和它本身以外没有其他因数的数。 根据引用[1][2][4]中的示例，我们可以采用以下思路： 1. 如果输入的数小于等于1，则不是素数（因为素数定义要求大于1）。 2. 对于大于1的数，我们只需要检查从2到该数的平方根（因为如果有一个大于平方根的因数，必然有一个小于平方根的因数）或者到该数减1（但为了效率，一般用平方根）。 但是注意，引用中的示例代码有几种写法：有到m/2的（引用1），有到x-1的（引用2），也有到i（即自身）的（引用4）。为了效率，我们通常使用平方根作为循环上限。 然而，引用[4]中提到了一个方法：循环从2开始到m（即该数本身），然后在循环中判断是否有因数。但这样效率较低。我们改进为循环到sqrt(m)即可。 具体步骤： - 输入一个正整数n。 - 如果n<=1，则不是素数。 - 如果n==2，则是素数。 - 如果n是偶数（且不等于2），则不是素数（除了2以外的偶数都不是素数）。 - 然后检查从3开始到sqrt(n)的所有奇数（因为偶数已经被排除），看是否有因数。 但是为了简单起见，我们可以写一个循环从2到sqrt(n)（包含sqrt(n)），如果其中有一个数能整除n，则n不是素数；否则是素数。 注意：在循环中，我们可以跳过偶数（除了2），但为了代码清晰，我们也可以直接循环所有整数（从2到sqrt(n)）。不过，我们可以先判断2，然后从3开始每次加2（只检查奇数）。 这里我们采用以下方法： 方法1（简单，但效率稍低）：循环从2到sqrt(n)（包括sqrt(n)），逐个判断。 方法2（优化）：先判断2，然后从3开始每次加2（只判断奇数）。 我们选择方法2，因为当n很大时，可以节省一半的时间。 但是，注意特殊情况：当n=2时，是素数；当n是偶数且大于2时，不是素数。 因此，我们可以这样写： 1. 如果n < 2，不是素数。 2. 如果n == 2，是素数。 3. 如果n % 2 == 0（且n不等于2），则不是素数。 4. 否则，n是大于2的奇数，那么只需要检查从3到sqrt(n)之间的奇数（包括sqrt(n)）是否有因数。 另外，我们也可以用一个标志变量（如isPrime）来记录是否是素数。 参考引用[2]中使用了isPrime变量，我们也可以采用这种方式。 代码步骤： 1. 输入一个正整数n。 2. 设置一个标志变量isPrime，初始化为1（表示是素数）。 3. 判断n是否小于2，如果是，则isPrime=0。 4. 如果n==2，则isPrime=1。 5. 如果n>2，则先判断是否为偶数（n%2==0），如果是，则isPrime=0。 6. 否则，n是大于2的奇数，循环从3开始到sqrt(n)（包括sqrt(n)），步长为2（即每次加2），判断n是否能被当前数整除。如果能，则isPrime=0，并跳出循环。 7. 根据isPrime的值输出结果。 注意：循环的上限是sqrt(n)，我们可以用整数i，条件为i*i<=n。 另外，我们也可以使用数学库中的sqrt函数，但需要包含math.h。为了避免使用浮点数，我们通常用i*i<=n作为条件。 代码示例： 我们写一个不使用math.h的版本，用整数循环。 具体代码： ``` #include <stdio.h> int main() { int n, i; int isPrime = 1; // 假设是素数 printf("请输入一个正整数："); scanf("%d", &n); // 判断小于2的情况 if (n < 2) { isPrime = 0; } else if (n == 2) { isPrime = 1; } else if (n % 2 == 0) { // 偶数（除了2）都不是素数 isPrime = 0; } else { // 检查从3到sqrt(n)的奇数 // 注意：n是大于2的奇数 for (i = 3; i * i <= n; i += 2) { if (n % i == 0) { isPrime = 0; break; } } } if (isPrime) { printf("%d是素数。\n", n); } else { printf("%d不是素数。\n", n); } return 0; } ``` 但是，上面的代码在n=2时，会进入else if (n==2)分支，设置isPrime=1；在n=3时，不会进入for循环（因为3*3=9>3，所以循环条件不满足），所以isPrime保持1，正确。 另一种写法：我们可以将n=2的情况合并到偶数判断之前，或者用另一种逻辑。上面的代码是清晰的。 不过，我们也可以不单独判断2，因为2是偶数，但我们在偶数判断中单独处理：当n==2时，我们并不进入偶数分支（因为我们在n==2时已经处理了）。实际上，我们可以调整一下顺序： 另一种写法： ``` #include <stdio.h> int main() { int n, i; int isPrime = 1; // 假设是素数 printf("请输入一个正整数："); scanf("%d", &n); if (n < 2) { isPrime = 0; } else if (n == 2) { isPrime = 1; } else if (n % 2 == 0) { isPrime = 0; // 包括n=4,6,8... } else { // n为大于2的奇数 for (i = 3; i * i <= n; i += 2) { if (n % i == 0) { isPrime = 0; break; } } } // 输出结果 if (isPrime) { printf("%d是素数。\n", n); } else { printf("%d不是素数。\n", n); } return 0; } ``` 这个程序可以正确判断。 但是，我们考虑n=1的情况，根据第一个分支，n<2，所以isPrime=0，输出“1不是素数”，正确。 另外，我们也可以不用单独处理2，因为2是偶数，但如果我们把偶数判断放在前面，那么2会被判断为不是素数（因为2%2==0），所以我们需要在偶数判断中排除2。因此，我们可以调整： 改进：先判断2，然后再判断其他偶数。 或者，我们可以这样写： ``` #include <stdio.h> int main() { int n, i; int isPrime = 1; printf("请输入一个正整数："); scanf("%d", &n); if (n < 2) { isPrime = 0; } else { // 检查2 if (n % 2 == 0) { // 如果n是2，那么是素数；否则不是 if (n == 2) { isPrime = 1; } else { isPrime = 0; } } else { // 对于大于2的奇数，需要检查 if (n == 2) { // 已经处理过2，所以这里n>2的奇数，但是n可能是1？不，因为n>=2，所以这里n>=3的奇数 for (i = 3; i * i <= n; i += 2) { if (n % i == 0) { isPrime = 0; break; } } } } } // 这样写复杂了，不如前面清晰。 // 所以还是用前面的写法。 ``` 因此，我们推荐第一种写法。 但是，我们还可以简化：将2和偶数判断合并，但需要小心。 我们可以这样： 1. 如果n<2，不是素数。 2. 如果n==2，是素数。 3. 如果n>2，那么： 如果n是偶数（则必然不是素数，除了2，但2已经排除），所以直接判断为不是素数。 如果n是奇数，则循环判断。 所以，我们写一个更简洁的： ``` #include <stdio.h> int main() { int n, i; printf("请输入一个正整数："); scanf("%d", &n); if (n < 2) { printf("%d不是素数。\n", n); return 0; // 直接结束 } // 处理2 if (n == 2) { printf("%d是素数。\n", n); return 0; } // 处理偶数（除了2） if (n % 2 == 0) { printf("%d不是素数。\n", n); return 0; } // 此时n是大于2的奇数 for (i = 3; i * i <= n; i += 2) { if (n % i == 0) { printf("%d不是素数。\n", n); return 0; // 发现因数，直接结束 } } // 循环结束都没有因数，则是素数 printf("%d是素数。\n", n); return 0; } ``` 这个版本没有使用isPrime变量，而是通过多个return返回。这样代码更简洁，但有些人可能认为多个return不好。不过对于小程序来说，这样可以接受。 我们选择这个版本。 但是，注意：当n=9时，循环从i=3开始，3*3=9<=9，然后9%3==0，所以输出不是素数，正确。 当n=25时，i=3: 3*3=9<=25 -> 25%3!=0；i=5:5*5=25<=25，25%5==0，输出不是素数，正确。 当n=49时，i=3,5,7（7*7=49<=49，49%7==0），输出不是素数。 当n=3,5,7时，循环条件：i=3时，对于n=3：3*3=9>3，所以不进入循环，直接输出是素数。 因此，这个程序是正确的。 我们输出代码：</think>以下是使用C语言编写的判断正整数是否为质数的程序。质数（素数）是指大于1且除了1和它本身外没有其他因数的数。 ```c #include <stdio.h> #include <math.h> // 包含sqrt函数 int main() { int n, i; int isPrime = 1; // 标志变量：1表示质数，0表示非质数 printf("请输入一个正整数："); scanf("%d", &n); // 处理特殊情况 if (n <= 1) { isPrime = 0; } // 单独处理2（唯一的偶质数） else if (n == 2) { isPrime = 1; } // 排除所有偶数 else if (n % 2 == 0) { isPrime = 0; } // 检查奇数 else { // 只需检查到平方根 int limit = (int)sqrt(n) + 1; for (i = 3; i <= limit; i += 2) { // 每次+2，只检查奇数 if (n % i == 0) { isPrime = 0; break; } } } // 输出结果 if (isPrime) { printf("%d 是质数\n", n); } else { printf("%d 不是质数\n", n); } return 0; } ``` ### 程序说明： 1. **输入处理**：读取用户输入的正整数 2. **特殊值处理**： - ≤1 的数不是质数 - 2 是唯一的偶质数 3. **优化检查**： - 排除所有偶数（除2外） - 只需检查到 $\sqrt{n}$（数学定理：若 $n$ 有因数，必有一个 $\leq \sqrt{n}$） - 只检查奇数（偶数已排除） 4. **标志变量**：`isPrime` 记录结果 5. **结果输出**：根据标志变量输出结论 ### 算法优化点： 1. 时间复杂度从 $O(n)$ 优化到 $O(\sqrt{n})$ 2. 减少循环次数：只检查奇数 3. 特殊处理2和偶数 4. 使用平方根作为上限（$\sqrt{n}$ 原理） ### 示例测试： - 输入 `7` → 输出 `7 是质数` - 输入 `9` → 输出 `9 不是质数` - 输入 `1` → 输出 `1 不是质数` - 输入 `2` → 输出 `2 是质数`