UVA516
感觉自己的思维不够灵动变通。。。特别是写了最近的几道题目之后。。。感觉得做出加倍努力不然真的就学不进去了。。我太难了。
#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <sstream> using namespace std; int const N = 47000; bool visit[N] = {true,true,false};//筛法获取素数表 vector <int> prime,result;//存放质数,输出结果 inline void setPrime(){//素数打表 for( int i=2; i<N; ++i){ if( !visit[i]){ prime.push_back(i); for( int j=i+i; j<N; j+=i) visit[j] = true; } } } int main(){ setPrime(); string line; while( getline(cin,line)){ if( '0'==line[0] ) break; long long temp = 1; int base,power; istringstream ss( line); while( ss >> base >> power){ while( power--) temp *= base; } temp -= 1; //依题意，任一行数字的最终大小结果 for( int i=prime.size()-1; i>=0; --i){//忘记减一会导致出错 if( !( temp % prime[i])){ int Count = 1;//记录当前素数质因子的个数 result.push_back( prime[i]);//自大到小存素数质因子(底数) temp /= prime[i];//相应变小 while( !( temp % prime[i])){ Count++; temp /= prime[i]; } result.push_back( Count);//对应的指数 } } for(unsigned int i=0; i<result.size(); ++i){ if( i != result.size()-1 )//大一经常碰到过的输出格式 printf("%d ",result[i]); else printf("%d\n",result[i]); } result.clear();//别忘记了初始化容器 } return 0; }
这里用到的素数线性筛法，应该是改进之后的晒法模板了。。。算是对之前说过的晒法的对比和补充吧。
之前的素数筛法打表
2017年03月12日 18:18:32 书
