素數(shù),也稱質(zhì)數(shù),指的是除了1和它本身以外,無法被其他整數(shù)整除的數(shù)。例如,17就是一個素數(shù),因為它無法被2到16之間的任何整數(shù)整除。
關(guān)于判斷一個數(shù)是否為素數(shù)的思路有兩種。第一種是,只需要將該數(shù)被2到該數(shù)減1之間的每一個整數(shù)去除,如果都無法被整除,那么該數(shù)就是素數(shù)。第二種思路更為簡潔,無需遍歷到該數(shù)減1,只需遍歷到該數(shù)的平方根即可。因為如果該數(shù)能被2到該數(shù)減1之間的任何整數(shù)整除,那么它的兩個因子必定有一個小于或等于它的平方根,另一個大于或等于它的平方根。
以17為例,我們只需要將17被2到4之間的每一個整數(shù)去除,都無法整除,所以我們可以判斷17是素數(shù)。
拓展來說,素數(shù)有無數(shù)個,它們在大于1的自然數(shù)中,除了1和它本身以外不再有其他因數(shù)。
對于素數(shù)的判斷,可以通過編程來實現(xiàn)。例如使用C語言,這是一種面向過程、抽象化的通用程序設(shè)計語言,廣泛應(yīng)用于底層開發(fā)。它能夠以簡易的方式編譯、處理低級存儲器,是一種僅產(chǎn)生少量機器語言且不需要任何運行環(huán)境支持便能運行的高效率程序設(shè)計語言。
以下是使用C語言判斷1到20之間的素數(shù)的程序。程序的主要思路是使用兩層循環(huán),外層循環(huán)遍歷1到20之間的整數(shù),內(nèi)層循環(huán)遍歷當(dāng)前數(shù)除去1和自身后的所有數(shù),判斷是否有整除的情況。如果存在因子,則說明該數(shù)不是素數(shù);如果內(nèi)層循環(huán)遍歷完畢后,未發(fā)現(xiàn)因子,則說明該數(shù)是素數(shù),將其輸出即可。
根據(jù)素數(shù)的性質(zhì),還可以設(shè)計其他判斷素數(shù)的程序。例如,判斷一個數(shù)是否能被1到該數(shù)減1之間的整數(shù)整除,或者判斷一個數(shù)是否能被2到該數(shù)的平方根之間的整數(shù)整除。如果不能被這些數(shù)中的任何一個整除,則該數(shù)為素數(shù)。
以上程序可以使用Visual C++ 6.0等開發(fā)工具進行編寫和調(diào)試。首先新建C++源文件,然后輸入預(yù)處理命令和主要函數(shù),定義變量并輸入數(shù)字,使用for和if函數(shù)判斷是否為素數(shù)。最后單擊OK創(chuàng)建新程序,隨機輸入一個數(shù)字來驗證新創(chuàng)建的C語言程序是否正確。if(i<=k) printf("這不是一個素數(shù)。");
else printf("這是一個素數(shù)。");
return 0;
擴展材料:
1. 素數(shù)的定義是只能被1和它本身整除,1不是素數(shù)。因此要判斷一個數(shù)是否為素數(shù),就要判斷它能不能被比他小的所有素數(shù)整除,這是一個算法。(寫到算法時,我只能寫出用它除以比他小的所有數(shù),造成運算速度低下)
2. 如果一個質(zhì)數(shù)大于根號n,而n可以除盡它,那么n必然也可以除盡一個更小的質(zhì)數(shù)。由此可以得到一個法2較快的素數(shù)判斷算法
參考資料:百度百科-scanf
參考資料:百度百科-質(zhì)數(shù)