自己写的
#include
#include
const int maxn1 = 100010;
typedef long long ll;
struct Piki{
ll pi;
int ki;
}s[maxn1];
bool isPrime(ll n) {
if(n == 1) return false;
ll sqr = (ll)sqrt(1.0 * n); // 开根号
for(int i = 2; i <= sqr; i++) {
if(n % i == 0) return false;
}
return true;
}
int much(ll a, ll b) {
int ans = 1;
if(b != 0 && b % a == 0 && isPrime(a)) {
ans += much(a, b / a);
}
return ans;
}
int main() {
ll n;
int ans = 0, j = 0;
scanf("%lld", &n);
ll sum = n;
ll maxn = (ll)sqrt(1.0 * n);
for(int i = 2; i <= maxn; i++) {
ans = much(i, n) - 1;
if(ans != 0) {
s[j].pi = i;
s[j].ki = ans;
j++;
n = n / (ll)pow(i, ans * 1.0);
}
}
if(j == 0) {
printf("%d=%d", sum, sum);
} else {
printf("%d=", sum);
for(int i = 0; i < j; i++) {
if(s[i].ki > 1) {
printf("%d^%d", s[i].pi, s[i].ki);
} else {
printf("%d", s[i].pi);
}
if(i < j - 1) printf("*");
}
}
printf("\n");
return 0;
}
算法笔记中的
#include
#include
const int maxn = 100010;
bool is_prime(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[maxn], pNum = 0;
void Find_Prime() {
for(int i = 1; i < maxn; i++) {
if(is_prime(i) == true) {
prime[pNum++] = i;
}
}
}
struct factor {
int x, cnt;
}fac[10];
int main() {
Find_Prime(); // 注意写出来
int n, num = 0;
scanf("%d", &n);
if(n == 1) printf("1=1");
else {
printf("%d=", n);
int sqr = (int)sqrt(1.0 * n); // 乘以1.0使其变为浮点型
for(int i = 0; i < pNum && prime[i] <= sqr; 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;
}
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);
}
}
}
return 0;
}
