【C素數】素數（質數）和分解質因數

種一棵樹最好的時間是十年前，其次是現在

文章目錄

• ​​判斷一個數是否是素數​​

• ​​1-1.基本概念：​​
• ​​1-2.題目描述：​​
• ​​1-3.題解思路：​​
• ​​1-4代碼實作​​

• ​​1-4-1方法一：直接flag标記法：​​
• ​​1-4-2方法二：函數法：​​

• ​​2-1基本概念​​
• ​​2-2分解質因數和最大質因數​​
• ​​2-3題目描述​​
• ​​2-4解題思路​​
• ​​2-5代碼實作​​

• ​​2-5-1方法：函數遞歸法：​​

判斷一個數是否是素數

部落客今天在複習C語言的時候遇到質因數，發現這個知識點忘記了，故有了此篇

先來複習一下概念吧：

一.素數

1-1.基本概念：

• .質數：質數又叫素數，素數是指在正整數範圍内，大于0并且隻能被1和自身整除的數
• 1不是素數 ，最小的素數是2
• 舉20以内的素數為例：2, 3，5 , 7，11, 13, 17, 19

1-2.題目描述：

給你一個數，判斷他是否是素數？

1-3.題解思路：

1. 如果輸入的數為1，則直接判斷為不是素數
2. 如果輸入的數不為1.則從<2–sqrt(n)>循環周遊，看他能否被整除
3. 如果有一個被整除就是素數，并break循環（隻有有一個能被整除就能判為素數）
4. 如果循環結束後，仍然不能被整除，就判斷為是素數

說明：為什麼是從<2–根号n>循環周遊?而不是從2到n-1?

解釋：如果輸入的數有一個因子範圍在sqrt(n)–n中，那麼必然就有一個因子位于2–根号n範圍内,例如16=2*8,如果找到了16能被2整除,就沒必要找16能被8整除了;

注意開根号函數sqrt（n）要引用頭檔案#include<math.h>

1-4代碼實作

使用flag=0标記，如果整除就改變flag=1,如果循環結束後flag仍為0就說明不能被<2–sqrt(n)>整除。

1-4-1方法一：直接flag标記法：

int main()
{
  int flag = 0;
  int n = 0;
  scanf("%d", &n);

  if (n == 1)
  {
    printf("%d不是素數\n",n);

  }
  for (int i = 2; i < sqrt(n); i++)
  {
    if (n % i == 0)
    {
      printf("%d不是素數\n",n);
      flag = 1;
      break;
    }
  }
  if (flag == 0)
  {
    printf("%d是素數\n",n);
  }

}      

1-4-2方法二：函數法：

int is_prime(int n)
{
  if (n == 1)
    return 0;
  for (int i = 2; i < sqrt(n); i++)
  {
    if (n % i == 0)
    {
      return 0;//一旦被整除,說明n不是素數,不是素數就傳回0
    }
  }
  return 1;//是素數就傳回1
}

int main()
{
  int n = 0;
  scanf("%d", &n);
  int ret = is_prime(n);
  if (ret == 1)
  {
    printf("%d是素數\n",n);
  }
  
  else
  {
    printf("%d不是素數\n",n);

  }
  return 0;
}      

二：合數

2-1基本概念

• 與素數相對，大于1的整數中，除了1和他本身外，還能被其他正整數整除的數
• 最小的合數是4（🤣1既不是素數又不是合數）
• 舉20以内的合數：4, 6，8, 9，10, 12，15, 16，，18 ， 20

關于素數和合數的概念小趣味知識：

1.🚗1既不是素數又不是合數

2.🚗大于2的素數都是奇數，2是唯一是偶數的素數

3.🚗大于1的整數中，不是素數就是合數

3.🚗最小的素數和合數都是偶數

2-2分解質因數和最大質因數

• 分解質因數定義：把一個合數用質數相乘的形式表現出來
• 分解質因數是一個過程，而最大質因數是通過這個過程分解出來的最大的質數
• 分解質因數的操作方法：短除法

想要了解短處法？速戳​​分解質因數連結​​

• 質數不能分解質因數的原因:質數隻能寫成1和他本身相乘的形式，而1不是質數，
• 例如将42分解質因數：42=237 是以最大質因數就是7

除到7後2-sqrt(7)内的數都不能再被整除，是以得到了最大質因數

2-3題目描述

2-4解題思路

短除法

通過不斷的遞歸調用，判斷42是否是質數

2-5代碼實作

注意：本題的600851475143資料範圍過大，已超過int的最大範圍，應使用long long類型定義變量，才能開辟足夠容納他的空間

2-5-1方法：函數遞歸法：

long long fun(long long n)
{
  if (n == 1)
  {
    return 1;
  }
  for (int i = 2; i < sqrt(n); i++)
  {
    if (n % i == 0)
    {
      return fun(n/i);
    }
  }
  return n;//7是從這裡出來的嘻嘻

int main()
{

  long long  n;
  while (scanf("%lld", &n) != EOF)
  {
    long long ret = fun(n);
    printf("%lld\n", ret);
  }
  return 0;

}