64541

浙大 PAT 甲级 1059 Prime Factors 质因数分解

先说测试点Question。如果是测点3没过,不是你的错,反而是你数学理论基础很好,因为通常不认为1是质数,而这个测点却输入了1,并且要求输出1。

这题就是基础的分解素因数,在王道论坛机试指南里有一小节专门谈这个Question。

#include<stdio.h> #include<Windows.h> bool mark[400001]; int prime[400001]; int primeSize; void init() { primeSize = 0; for (int i = 2; i <= 400000; i++) { if (mark[i] == true) { continue; } prime[primeSize++] = i; if (i >= 1000) { continue; } for (int j = i*i; j <= 400000; j += i) { mark[j] = true; } } } // 用素数筛法筛选出2到400000内的所有素数 int main() { init(); int N; scanf("%d", &N); printf("%d=", N); if (N == 1) { printf("1\n"); return 0; } int ansPrime[100]; // 按顺序保存分解出的素因数 int ansSize = 0; // 分解出素因数的个数 int ansNum[100]; // 保存分解出的素因数对应的幂指数 for (int i = 0; i < primeSize; i++) // 依次测试每一个素数 { if (N%prime[i] == 0) // 若该素数能整除被分解数 { ansPrime[ansSize] = prime[i]; ansNum[ansSize] = 0; // 初始化幂指数为0 while (N%prime[i] == 0) // 从被测试数中将该素数分解出来,并统计其幂指数 { ansNum[ansSize]++; N /= prime[i]; } ansSize++; // 素因数个数增加 if (N == 1) // 若已被分解成1,则分解提前终止 { break; } } } if (N != 1) // 若测试完2到400000内所有素因数,N仍未被分解至1,则剩余的因数一定是n一个大于400000的素因数 { ansPrime[ansSize] =N; // 记录该最大素因数 ansNum[ansSize++] = 1; // 其幂指数只能为1 } for (int i = 0; i < ansSize; i++) { if (i == ansSize - 1) { if (ansNum[i] > 1) { printf("%d^%d\n", ansPrime[i], ansNum[i]); } else { printf("%d\n", ansPrime[i]); } } else { if (ansNum[i] > 1) { printf("%d^%d*", ansPrime[i], ansNum[i]); } else { printf("%d*", ansPrime[i]); } } } return 0; }

来源:51CTO

作者:马铃薯小弟

链接:https://blog.csdn.net/qq_39115541/article/details/100126368

Recommend