篩選法不僅能夠用來計算最小的若干素數，也可以用來求整數的最大公因子。

問題鏈接：HDU2136 Largest prime factor。基礎訓練級的題，用C語言編寫。

這個問題，對于輸入的n，并不是要求輸出n的最大公因子的值，而是輸出n的最大公因子的素數序號，即LPF(n)。

眾所周知，LPF(2)=1,LPF(3)=2,LPF(4)=1,LPF(5)=3,......

AC通過的C語言程序如下：

/* HDU2136 Largest prime factor */#include <stdio.h>#define MAXN 1000000// 若primefactor[i] = x，則x為i的最大因子（素數）的序號 int primefactor[MAXN+1] = {0, 0};void maketabel(int n) {int count, i, j;// 對于偶數，令其因子暫時為２，即第１個for(i=2; i<=n; i+=2)primefactor[i] = 1;// 對于奇數，令其因子暫時為其值for(i=3; i<=n; i+=2)primefactor[i] = i;// 對于素數i，設置j=k*i的暫時因子為i，有更大因子則會被逐步更新count = 1;for(i=3; i<=n; i+=2)if(i == primefactor[i]) {count++;primefactor[i] = count;for(j=2*i; j<=n; j+=i)primefactor[j] = count;} }int main(void) {int n;maketabel(MAXN);while(scanf("%d", &n) != EOF)printf("%d\n", primefactor[n]);return 0; }

轉載于:https://www.cnblogs.com/tigerisland/p/7564553.html

總結

以上是生活随笔為你收集整理的HDU2136 Largest prime factor的全部內容，希望文章能夠幫你解決所遇到的問題。

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