C語言中判斷素數(求素數)的思路與方法實例

 更新時間:2022年03月10日 11:58:09   作者:烏龜蓋瑞  
計算機或者相關專業基本上大一新生開始學編程都會接觸的一個問題就是判斷質數,下面這篇文章主要給大家介紹了關于C語言中判斷素數(求素數)的思路與方法,需要的朋友可以參考下

前言

素數又稱質數。所謂素數是指除了 1 和它本身以外,不能被任何整數整除的數,例如17就是素數,因為它不能被 2~16 的任一整數整除。

思路1):因此判斷一個整數m是否是素數,只需把 m 被 2 ~ m-1 之間的每一個整數去除,如果都不能被整除,那么 m 就是一個素數。

思路2):判斷方法還可以簡化。m 不必被 2 ~ m-1 之間的每一個整數去除,只需被 2 ~  之間的每一個整數去除就可以了。如果 m 不能被 2 ~  間任一整數整除,m 必定是素數。例如判別 17 是是否為素數,只需使 17 被 2~4 之間的每一個整數去除,由于都不能整除,可以判定 17 是素數。

原因:因為如果 m 能被 2 ~ m-1 之間任一整數整除,其二個因子必定有一個小于或等于 ,另一個大于或等于 。例如 16 能被 2、4、8 整除,16=2*8,2 小于 4,8 大于 4,16=4*4,4=√16,因此只需判定在 2~4 之間有無因子即可。

思路1實現:

#include <stdio.h>
int main() {
    int n;
    printf("請輸入一個1-100之間的整數:\n");
    scanf("%d", &n);
 
    int m = 0;
    for (int i = 2; i < n; i++ ) {
        if(n % i  == 0) {
            m++;
        }
    }
    if (m == 0) {
        printf("%d是素數\n", n);
    } else {
        printf("%d不是素數\n", n);
    }
    return 0;
}

思路2實現:

#include <stdio.h>
#include <math.h>
int main() {
    int n;
    printf("請輸入一個1-100之間的整數:\n");
    scanf("%d", &n);
 
    int i = 0;
    int q = sqrt(n);
    for (i = 2; i <= q; i++ ) {
        if(n % i  == 0) {
            break;
        }
    }
    if (i > q) {
        printf("%d是素數\n", n);
    } else {
        printf("%d不是素數\n", n);
    }
 
    return 0;
}

《C與指針》4.14 - 2:

打印1~100之間所有質數:

#include <stdio.h>
int main() {
    int num, divisor;
    printf("1, 2");
    for (num = 3; num <= 100; num += 2) {
        for(divisor = 3; divisor < num; divisor +=2 ) {
            if (num % divisor == 0) {
                break;
            }
        }
 
        if(divisor >= num) {
            printf(", %d", num);
        }
    }
    printf("\n");
    return 0;
}

結果:

1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

補充:判斷素數的4種方法實例

#include<stdio.h>
#include<math.h>
//方法一:從1-n挨個判斷;
 bool isPrimel_1(int n) 
{	for(int i=2;i<n;i++)
	if(n%i==0)
	return false;
	return true;
}

//方法二: 將被判斷數n,進行開方作為判斷結束的條件,
//因為開方后的數,是n的最大因子,最大因子之后的數對判斷該數是否是素數沒有意義。

bool isPrimel_2(int n)  
{	for(int i=2;i<sqrt(n);i++)
	if(n%i==0)
	return false;
	return true;
}

//方法三: 只需要判斷到該數的一半即可,如果超過它本身的一半,
//進行求余的結果將永遠不會為0,除非是該數對該數的求余。

bool isPrimel_3(int n)  
{   int i;
    if(n%2==0)
    return 0;
    for(i=3;i=n/2;i+=2){
	 if(n%i==0)
     return 0;
     return 1;
}
}

 //方法四:從3-n,只判斷奇數,先對一個數進行奇偶判斷,若是奇數,
 //只對從3到它本身的奇數進行求余計算,同理若是偶數,一定不是素數。
 
bool isPrimel_4(int n)
{   int i,j=1;
    if(n%2==0)
    return 0;
    else{
    for(i=3;i<=n;i=i+2){
	 if(n%i==0)	
	 j=i;
	 break;
	}
}
   if(j==n)
   return 0;
   return 1;
}

int  main()
{
	int n;
	printf("請輸入一個數:");
	scanf("%d",&n); 
	printf("%d,%d,%d,%d\n",isPrimel_1(n),isPrimel_2(n),isPrimel_3(n),isPrimel_4(n));
	return 0;
}

總結

到此這篇關于C語言中判斷素數(求素數)的文章就介紹到這了,更多相關C語言判斷素數內容請搜索腳本之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持腳本之家!

相關文章

  • C++11 Unicode編碼轉換

    C++11 Unicode編碼轉換

    這篇文章主要介紹了C++11 Unicode編碼轉換的相關資料,幫助大家更好的理解和學習c++11,感興趣的朋友可以了解下
    2020-08-08
  • C/C++中棧(stack)&堆(heap)詳解及其作用介紹

    C/C++中棧(stack)&堆(heap)詳解及其作用介紹

    這篇文章主要介紹了C/C++中棧(stack)&堆(heap)詳解及其作用,本文給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2021-09-09
  • 詳解C++11中的右值引用與移動語義

    詳解C++11中的右值引用與移動語義

    本篇文章主要介紹了詳解C++11中的右值引用與移動語義,小編覺得挺不錯的,現在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2017-02-02
  • C++實現修改函數代碼HOOK的封裝方法

    C++實現修改函數代碼HOOK的封裝方法

    這篇文章主要介紹了C++實現修改函數代碼HOOK的封裝方法,有助于深入了解C++的HOOK原理,需要的朋友可以參考下
    2014-10-10
  • C++實現刪除txt文件中指定內容的示例代碼

    C++實現刪除txt文件中指定內容的示例代碼

    這篇文章主要介紹了C++實現刪除txt文件中指定內容的示例代碼,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2020-12-12
  • 一篇文章帶你使用C語言編寫內核

    一篇文章帶你使用C語言編寫內核

    內核是操作系統最核心的內容,主要提供硬件抽象層、磁盤及文件系統控制、多任務等功能,由于其涉及非常廣泛的計算機知識,很少被人們所熟悉,因而披上了一層神秘的面紗
    2021-08-08
  • 詳解Bucket Sort桶排序算法及C++代碼實現示例

    詳解Bucket Sort桶排序算法及C++代碼實現示例

    桶排序是一種線性排序算法,這里我們來詳解Bucket Sort桶排序算法及C++代碼實現示例,需要的朋友可以參考下
    2016-07-07
  • 基于OpenCv的運動物體檢測算法

    基于OpenCv的運動物體檢測算法

    這篇文章主要為大家詳細介紹了基于OpenCv的運動物體檢測算法,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2018-01-01
  • 淺談c語言中轉義字符的用法及注意事項

    淺談c語言中轉義字符的用法及注意事項

    下面小編就為大家帶來一篇淺談c語言中轉義字符的用法及注意事項。小編覺得挺不錯的,現在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2016-08-08
  • C++ list的實例詳解

    C++ list的實例詳解

    這篇文章主要介紹了 C++ list的實例詳解的相關資料,希望通過本文大家能夠理解掌握這部分內容,需要的朋友可以參考下
    2017-09-09

最新評論

免费人成视频在线观看