POJ 1365 Prime Land 整数分解

本文主要是介绍POJ 1365 Prime Land 整数分解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题解：

在求素数的过程中记录下每个数的最小因素，a[n]表示n的最小因素，例如a[2]=2, a[12] = 3, a[16] = 2······

#include<cstdio>
#include<cstring>
#include<memory>
#include<cmath>
using namespace std;const int MAX = 33333;int a[MAX], p[MAX];
int r, pn;
struct Result { int p, e; } res [1000];void prime ()
{memset(a,0,sizeof(a));int i, j;pn = 0;for ( i = 2; i < MAX; i++ ){if ( a[i] == 0 ) p[pn++] = i;for ( j = 0; j < pn && i * p[j] < MAX && ( p[j] <= a[i] || a[i] == 0 ); j++ )a[i*p[j]] = p[j];}
}void split ( int n )
{int m = n;r = -1;while ( a[n] ){r++;res[r].p = a[n];res[r].e = 0;while ( m % a[n] == 0 ){res[r].e++;m = m / a[n];}n = m;}if ( n != 1 ){r++;res[r].p = n;res[r].e = 1;}
}int main()
{prime();char str[10000];while ( gets(str) ){if ( str[0] == '0' ) break;int num = 1,len = strlen(str);int  i = 0, P, E;while ( i < len ){P = 0;while ( str[i] != ' ' ){P = P * 10 + str[i] - '0';i++;}i++; E = 0;while ( str[i] != ' ' && i < len ){E = E * 10 + str[i] - '0';i++;}i++;num = num * pow(P+0.0,E);}split(num-1);for ( i = r; i > 0; i-- )printf("%d %d ",res[i].p, res[i].e);printf("%d %d\n",res[i].p, res[i].e);}return 0;
}

这篇关于POJ 1365 Prime Land 整数分解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---