题目
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^211171011291
题目分析
输入一个整数N，将其分解为质因数的乘法式
解题思路
思路01
- 创建质数表
- 依次判断质数表中质数i，若N%i==0，则打印质数（并内循环统计i整除N的次数tm，每次内循环完成更新N=N/i，若N%i!=0，退出内循环）;
- 打印当前质数的指数tm
思路02
- 创建质数表-埃式筛法
- 筛选质数因子，并统计其次数
Code
Code 01
#include <iostream>
#include <cmath>
using namespace std;
bool isPrime(int n) {
if(n<=1)return false;
int sqr=(int)sqrt(1.0*n);
for(int i=2; i<=sqr; i++) {
if(n%i==0)return false;
}
return true;
}
int prime_table[100010];
bool prime_bool[100010];
void create_pt() {
int index = 0;
for(int i=2; i<100010; i++) {
if(prime_bool[i]==false) {
prime_table[index++]=i;
for(int j=i+i; j<100010; j+=i) {
prime_bool[j]=true;
}
}
}
}
int main(int argc,char *argv[]) {
// 1.创建素数表
create_pt();
// 2.接收输入
long long n;
scanf("%lld", &n);
// 3. 打印
printf("%lld=",n);
if(n==1)printf("1");
int index=0;
bool wf = false; //false为打印的第一个数字，true为打印的第一个数字后的数字
while(n>1) {
int prime = prime_table[index];
bool flag = false;
int tm=0;
while(n%prime==0) {
n/=prime;
tm++;
}
if(tm>0) {
if(wf)printf("*");
printf("%d",prime);
wf = true;
}
if(tm>1)printf("^%d",tm);
index++;
}
return 0;
}
Code 02（素数表生成简洁但不高效）
#include <cstdio>
#include <vector>
using namespace std;
vector<int> prime(500000, 1);
int main() {
for(int i = 2; i * i < 500000; i++)
for(int j = 2; j * i < 500000; j++)
prime[j * i] = 0;
long int a;
scanf("%ld", &a);
printf("%ld=", a);
if(a == 1) printf("1");
bool state = false;
for(int i = 2; a >= 2; i++) {
int cnt = 0, flag = 0;
while(prime[i] == 1 && a % i == 0) {
cnt++;
a = a / i;
flag = 1;
}
if(flag) {
if(state) printf("*");
printf("%d", i);
state = true;
}
if(cnt >= 2)
printf("^%d", cnt);
}
return 0;
}
Code 03
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
// 素数判断
//bool isPrime(int n) {
// if(n<=1)return false;
// int sqr=(int)sqrt(1.0*n);
// for(int i=2; i<=sqr; i++)
// if(n%i==0)return false;
// return true;
//}
// 素数表
const int maxn = 1000010;
int p[maxn],prime[maxn],pNum;
void prime_table() {
// 埃式筛法
for(int i=2; i<maxn; i++) {
if(p[i]==1)continue;
prime[pNum++]=i;
for(int j=i+i; j<maxn; j+=i)p[i]=1;
}
}
struct factor {
int x;
int cnt;
} fac[100];
int num;
void find_prime(int n) {
for(int i=0; i<=pNum&&prime[i]<=sqrt(n); i++) {
if(n%prime[i]==0) {
fac[num].x=prime[i];
fac[num].cnt=0;
while(n%prime[i]==0) {
fac[num].cnt++;
n/=prime[i];
}
num++;
}
if(n==1)break;
}
if(n!=1) {
fac[num].x=n;
fac[num].cnt=1;
num++;
}
}
void show(int n){
printf("%d=",n);
for(int i=0;i<num;i++){
if(i>0) printf("*");
printf("%d",fac[i].x);
if(fac[i].cnt!=1)printf("^%d",fac[i].cnt);
}
}
int main(int argc,char * argv[]) {
long long n;
scanf("%lld",&n);
if(n==1){
printf("1=1");
return 0;
}
prime_table();
find_prime(n);
show(n);
return 0;
}