[暑假集训--数论]hdu2136 Largest prime factor

Everybody knows any number can be combined by the prime number.
Now, your task is telling me what position of the largest prime factor.
The position of prime 2 is 1, prime 3 is 2, and prime 5 is 3, etc.
Specially, LPF(1) = 0.

InputEach line will contain one integer n(0 < n < 1000000).
OutputOutput the LPF(n).
Sample Input

Sample Output

对x分解质因数，问最大的质因子是第几大质数

瞎暴力就好

 #include<cstdio>

 #include<algorithm>

 #define LL long long

 using namespace std;

 inline LL read()

 {

     LL x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 int mk[];

 int pp[],len;

 int rnk[];

 int n;

 inline void getp()

 {

     for (int i=;i<=;i++)

     {

         if (!mk[i])

         {

             for (int j=*i;j<=;j+=i)mk[j]=;

             pp[++len]=i;

             rnk[i]=len;

         }

     }

 }

 int main()

 {

     getp();

     while (~scanf("%d",&n))

     {

         if (!mk[n]){printf("%d\n",rnk[n]);continue;}

         int mx=;

         for (int i=;i<=len;i++)

         {

             if (pp[i]*pp[i]>n)break;

             if (n%pp[i]==)mx=i;

             while (n%pp[i]==)n/=pp[i];

         }

         if (n!=)mx=rnk[n];

         printf("%d\n",mx);

     }

 }

hdu 2136

巴特西

[暑假集训--数论]hdu2136 Largest prime factor

最新文章

热门文章