題目描述：

題目大意：找出具有最大素數(shù)因子的整數(shù)。如果有不止一個，則輸出在輸入文件中出現(xiàn)最早的一個。

解題思路：剛開始時，p數(shù)組中的元素全為0，剛開始對于素數(shù) i,p[i]=0,用一個for循環(huán)，將是素數(shù) i 的倍數(shù)的數(shù) 的在數(shù)組p中的值全部賦值為 i；

如：第一輪：2為素數(shù)，p[2]=0,p[4]=2,p[6]=2,p[8]=2......p[2*n]=2;

? ? ? 第二輪：3為素數(shù),? p[3]=0,p[6]=3,p[9]=3,p[12]=3......p[3*n]=3;

? ? ?? 第...輪：i為素數(shù)，p[i]=0,p[i+n*i]=i;

再如下列測試案例中 m=38時，在第一輪中，2為素數(shù)，38是2的倍數(shù)，所以p[38]=2;在第18輪（即i=19）時，19為素數(shù)，而38是19的倍數(shù)，所以p[38]更新為19

代碼實現(xiàn)：

#include<stdio.h> #include<iostream> const int MAX=20005; int p[MAX]; using namespace std; int main() {int n,s,m,maxn;int i,j;p[1]=1;for(i=2;i<MAX;i++){if(p[i]==0)for(j=i;j<MAX;j+=i)//這一段代碼不斷實現(xiàn)對p數(shù)組進(jìn)行更新p[j]=i;}while(~scanf("%d",&n)){maxn=-1;while(n--){scanf("%d",&m);if(p[m]>maxn){maxn=p[m];s=m;}}printf("%d\n",s);}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/LJHAHA/p/9991791.html

總結(jié)

以上是生活随笔為你收集整理的素数筛选-hdu2710的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。