正題

luogu題目鏈接:https://www.luogu.org/problemnew/show/CF735D

---

題目大意

將一個數分解成若干個數使得這若干個數的最大因子最小。

---

解題思路

如果是質數就是1。如果是偶數根據哥德巴赫猜想就是2。或者把一個奇數減去2后是個質數也是2。否則就是3。

---

$code$

#include<cstdio> using namespace std; int n; bool check(int n) {if(n<2) return 0;for(int i=2;i*i<=n;i++)if(n%i==0) return 0;return 1; } int main() {scanf("%d",&n);if(check(n)) putchar('1');else if(!(n&1)) putchar('2');else if(check(n-2)) putchar('2');else putchar('3'); }

總結

以上是生活随笔為你收集整理的CF735D-Taxes【数学,数论】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。