// zerojudge.tw 的 a010 質因數分解
// 建質數表較費事,若資料不多不一定要建表,像a007有十萬筆就一定要建表
#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
#define maxn 46340 // sqrt(2147483647) < 46341
using namespace std;
bool c[maxn+10]; //0~46340之間false為質數
vector <int> p; // 2~46340之間的質數共有 4792個
// p[4791]=46337 , p[4790]=46327,p[4792]=46349
//...