素数c语言程序实现方法从简单到高效解决运行卡顿问题

写素数 C 语言程序的时候，是不是遇到过这种情况？判断个两位数、三位数还行，一旦想算 10 万以上的素数，程序就卡得动不了，半天出不来结果？其实啊，不是你写的代码错了，可能是方法太简单，效率不够高。今天兔子哥就从最简单的方法说起，一步步教你怎么优化，让程序跑得又快又顺，解决卡顿问题，一起往下看吧！

---

一、最基础的方法：逐个判断（适合新手入门）

刚开始学写素数程序，大家肯定都会想到最直接的办法：拿一个数 n，从 2 开始一个个除到 n-1，看看有没有能整除的。
代码大概是这样的：
c运行

#include int is_prime(int n) {if (n <= 1) return 0;for (int i = 2; i < n; i++) {if (n % i == 0) return 0;}return 1;}int main() {int num;printf("请输入一个数：");scanf("%d", &num);if (is_prime(num)) {printf("%d是素数\n", num);} else {printf("%d不是素数\n", num);}return 0;}

运行效果：
输入 17，很快显示 “17 是素数”；但要是输入 100003 这种大数，就得等好几秒，甚至更久。
为啥会这样？因为它要循环到 n-1，n 越大，循环次数越多，电脑就忙不过来，自然就卡了。新手用这个方法入门没问题，但想算大数，肯定不行。

---

二、第一次优化：缩小循环范围（减少一半工作量）

你有没有想过，一个数 n 如果有因数，肯定有一个因数小于等于它的平方根。比如 36，平方根是 6，它的因数 2、3、4、6 都不超过 6。所以啊，咱们不用循环到 n-1，循环到√n 就行。
优化后的代码（核心部分）：
c运行

int is_prime(int n) {if (n <= 1) return 0;for (int i = 2; i * i <= n; i++) {  // 这里改成i*i <= nif (n % i == 0) return 0;}return 1;}

效果对比：

方法	计算 100003 所需循环次数	耗时（大概）
基础方法	100001 次	3 秒
优化方法	约 316 次	0.1 秒

是不是快多了？这一步优化很关键，能减少大量不必要的计算。兔子哥第一次用这个方法时，算大数的速度明显提升，当时就觉得 “原来还能这么省事儿”。

---

三、再进一步：排除偶数（减少一半循环）

除了 2 之外，所有素数都是奇数。那咱们可以先判断 n 是不是 2，如果不是，就只看奇数能不能整除它，这样又能少一半循环。
代码调整：
c运行

int is_prime(int n) {if (n <= 1) return 0;if (n == 2) return 1;  // 2是素数if (n % 2 == 0) return 0;  // 偶数直接排除for (int i = 3; i * i <= n; i += 2) {  // i从3开始，每次加2（只看奇数）if (n % i == 0) return 0;}return 1;}

有朋友可能会问，这样真的有用？你想啊，原来循环里有一半是偶数，现在全跳过了，循环次数又少了一半，能不快吗？算 100 万以上的数时，这个优化的效果会更明显。

---

四、高效方法：埃氏筛法（批量找素数超好用）

如果想找一定范围内的所有素数，比如 1 到 100 万的素数，前面的方法还是不够快。这时候可以用埃氏筛法，思路很巧妙：先假设所有数都是素数，然后把已知素数的倍数都标成非素数。
代码示例：
c运行

#include #include void sieve(int max) {int is_prime[max + 1];memset(is_prime, 1, sizeof(is_prime));  // 先全设为1（假设都是素数）is_prime[0] = is_prime[1] = 0;  // 0和1不是素数for (int i = 2; i * i <= max; i++) {if (is_prime[i]) {  // 如果i是素数，就把它的倍数标为非素数for (int j = i * i; j <= max; j += i) {is_prime[j] = 0;}}}// 打印素数for (int i = 2; i <= max; i++) {if (is_prime[i]) {printf("%d ", i);}}}int main() {sieve(100000);  // 找1到100000的素数return 0;}

解决卡顿的关键：
埃氏筛法不用逐个判断每个数，而是通过标记倍数来排除非素数，时间效率大大提高。算 1 到 100 万的素数，用这个方法眨眼就能出结果，而用基础方法可能要等几分钟。

---

五、新手常犯的卡顿问题及解决

1. 循环范围没控制好：总有人把循环写成 i <= n，这样算大数时循环次数太多。记住，i*i <= n 就够了。
2. 没排除偶数：明明除了 2 之外，偶数都不是素数，还一个个判断，纯纯浪费时间。
3. 批量找素数用错方法：想找 1 到 10 万的素数，还在用逐个判断的方法，不卡才怪，换成埃氏筛法就好。

---

兔子哥觉得，写程序就像走路，刚开始慢慢走（用简单方法）没问题，但走长途就得找捷径（优化方法）。素数程序的优化，核心就是减少不必要的计算 —— 能少循环一次就少一次，能排除的数就早点排除。
新手不用一开始就追求最高效的方法，先把基础方法弄懂，再一步步尝试优化，看着自己写的程序从卡顿到流畅，那种成就感特别棒。而且啊，这些优化思路不只是用在素数程序上，写其他程序时也能用，能让你的代码越来越 “聪明”。希望这些方法能帮到你，赶紧试试吧！

标签： 第一次 是不是