本人C語言萌新，最近工作中頻頻出現C語言小錯誤，遂決定使用笨方法提高我的C語言水平，堅持每天一個C語言小練習，養成C語言手感，從此讓編程成為習慣。
題目描述
統計100以內所有素數的個數
分析
素數（prime number）又稱質數，在大于1的自然數中，除了1和它本身以外不再有其他因數的數稱為質數，2是最小的素數。
代碼實現
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
#include <stdio.h>#define INTEGER_RANGE 100 //數字范圍int if_prime(int num);int main(){ int sum = 0; /* 2是最小的素數，for循環范圍為2-100 */ for(int i = 2; i <= INTEGER_RANGE; i++) { if(if_prime(i)) sum++; } printf("%d以內的素數個數為：%d\n", INTEGER_RANGE, sum); return 0;}/* * 判斷是否為素數，是則返回1，否返回0 * */int if_prime(int num){ int i = 0; for(i = 2; i < num; i++) { /* 如果該數有存在1以外的其他正因數，則不是素數 */ if(num % i == 0) return 0; } return 1;} |
運行結果
后期完善
這里只對if_prime(num)函數進行完善：
-
增加非法數字的判斷，
num小于2直接返回0 -
將循環范圍由
2~num-1改成2~sqrt(num)
至于為什么用sqrt,這里借用下別人的解釋（比較通俗易懂）
當一個數不是素數的時候，那這數肯定是除了它本身和1外的兩個數之積
（ a*b = m ),如果設a是小于或者等于b的數，那a肯定是小于等于m的開根，即a <= sqrt( m )。——百度貼吧（C語言吧）
還有一種用法是把num改成num/2，但是當num大于4時，sqrt(num)比num/2小，所以用sqrt(num)的效率比用num/2高。
至于為什么可以用num/2，這里也借用別人的解釋（有點難懂）
其實這是數學知識，n不除以2也行，只是運算量更大，其實最少運算量的方法是n開根號。
我證明一下合理性吧。用反證法。
如果一個數是合數，則一定能分解成兩個不是1的數相乘，所以能被分解成一個大于等于2的數和一個小于等于n/2相乘。
如果這個數沒有一個小于等于n/2的因數，那它一定不是合數，所以它一定是素數，不用再檢查后面的數了。這里是小于n/2，是因為如果這個數能被n/2整除，那2一定是它的因數，很容易知道2小于等于n/2，所以在檢查n/2之前一定檢查過2。證明完成！
n開根號也差不多這樣證明。——https://fishc.com.cn/thread-181309-1-1.html
如果你對上面的兩種用法都不理解，那記住它們就行了。。。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#include <math.h>/* * 判斷是否為素數，是則返回1，否返回0（改進版） * */int if_prime(int num){ if(num < 2) return 0; //最小的素數為2 int i = 0; //sqrt():開方函數（一定要寫小于等于） for(i = 2; i <= sqrt(num); i++) { /* 如果該數有存在1以外的其他正因數，則不是素數 */ if(num % i == 0) return 0; } return 1;} |
網上參考
原文鏈接：https://www.runoob.com/cprogramming/c-exercise-example36.html
sqrt()為開方函數，需要加math.h頭文件
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
// Created by www.runoob.com on 15/11/9.// Copyright © 2015年 菜鳥教程. All rights reserved.// #include<stdio.h>#include<math.h>int main(){ int i,j,k,n=0; for(i=2;i<=100;i++) { k=(int)sqrt(i); for(j=2;j<=k;j++) if(i%j==0) break; if(j>k) { printf("%d ",i); n++; if(n%5==0) printf("\n"); } } return 0;} |
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持服務器之家。
原文鏈接：https://blog.csdn.net/weixin_43772810/article/details/120212643
