PAT甲級本題1059 Prime Factors(25点)C++実現(素数覚書の作成)
14296 ワード
タイトル
Given any positive integer N, you are supposed to find all of its prime factors, and write them in the format N = p1^k1 * p2^k2 *…*pm^km.
Input Specification:
Each input file contains one test case which gives a positive integer N in the range of long int.
Output Specification:
Factor N in the format N = p1^k1 * p2^k2 *…*pm^km, where pi’s are prime factors of N in increasing order, and the exponent ki is the number of pi – hence when there is only one pi, ki is 1 and must NOT be printed out.
Sample Input: 97532468 Sample Output: 97532468=2^2*11*17*101*1291
構想
繰り返し演算を回避するために、素数テーブルprimeを維持し、{2}に初期化します.
Nを分解する時、まず素数表の中の数がその因子であるかどうかを考察する.素数テーブルに因子がなく、素数テーブルの最大値がルートNよりも小さい場合、ルートNを1つずつ考察し、発見されるたびに素数テーブルに保存する.
Nの因子mをfactor配列に保存し,n/mを反復的に考察する.因子がなければ,それ自体が素数でありfactorに保存される.
最後に、指定したルールに従って結果を出力します.
注意入力した値は1である可能性があり、単独で考慮する必要があります.そうしないと、テストポイント3は合格できません.
コード#コード#
Given any positive integer N, you are supposed to find all of its prime factors, and write them in the format N = p1^k1 * p2^k2 *…*pm^km.
Input Specification:
Each input file contains one test case which gives a positive integer N in the range of long int.
Output Specification:
Factor N in the format N = p1^k1 * p2^k2 *…*pm^km, where pi’s are prime factors of N in increasing order, and the exponent ki is the number of pi – hence when there is only one pi, ki is 1 and must NOT be printed out.
Sample Input: 97532468 Sample Output: 97532468=2^2*11*17*101*1291
構想
繰り返し演算を回避するために、素数テーブルprimeを維持し、{2}に初期化します.
Nを分解する時、まず素数表の中の数がその因子であるかどうかを考察する.素数テーブルに因子がなく、素数テーブルの最大値がルートNよりも小さい場合、ルートNを1つずつ考察し、発見されるたびに素数テーブルに保存する.
Nの因子mをfactor配列に保存し,n/mを反復的に考察する.因子がなければ,それ自体が素数でありfactorに保存される.
最後に、指定したルールに従って結果を出力します.
注意入力した値は1である可能性があり、単独で考慮する必要があります.そうしないと、テストポイント3は合格できません.
コード#コード#
#include
#include
#include
using namespace std;
vector<int> prime; //
vector<int> factor; //
bool isPrime(int n){
for (int i=2; i<=sqrt(n); i++){
if (n % i == 0){
return false;
}
}
return true;
}
void divide(int n){
if (n < 2){
return;
}
int len = prime.size();
int m = 0;
for (int i=0; i<len; i++){
if (n % prime[i] == 0) {
m = n / prime[i];
factor.push_back(prime[i]);
break;
}
}
if (m==0){ //n , N ,
for (int i=prime[len-1]+1; i<=sqrt(n); i++){
if (isPrime(i)){
prime.push_back(i);
if (n % i == 0){
m = n / i;
factor.push_back(i);
break;
}
}
}
}
if (m==0){ //n
factor.push_back(n);
return;
}
else {
divide(m);
}
}
int main(){
prime.push_back(2);
int n;
cin >> n;
cout << n << "=";
if (n==1){
cout << "1";
}
else{
divide(n);
int i = 0;
while (i<factor.size()){
if (i > 0){
cout << "*";
}
cout << factor[i];
int j = i + 1;
while (j<factor.size() && factor[j]==factor[i]){
j++;
}
int k = j - i;
if (k > 1){
cout << "^" << k;
}
i = j;
}
}
return 0;
}