[编程题]Prime Factors (25)
- 热度指数：8858 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
- 算法知识视频讲解
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.
输入描述:
Each input file contains one test case which gives a positive integer N in the range of long int.
输出描述:
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.
示例1
输入
97532468
输出
97532468=2^2*11*17*101*1291
#include <iostream>
#include <cmath>
using namespace std;
struct fac{ //x为质因子，cnt为其个数
int x,cnt;
}fac[20];
bool isprime(int n){ //判断是否为素数
if(n<=1) return false;
if(n==2) return true;
for(int i=2;i*i<=n;i++){
if(n%i==0) return false;
}
return true;
}
int main(){
int n,temp,num=0; //num为n的不同质因子个数
cin>>n;
temp=n;
if(n==1) cout<<"1=1"; //特例
else{
int sqr=(int)sqrt(1.0*n);
for(int i=2;i<=sqr;i++){
if(isprime(i)){ //若为素数
if(n%i==0){ //且为n的因子
fac[num].x=i; //先记录该因子并初始化个数
fac[num].cnt=0;
while(n%i==0){ //计算该质因子个数
fac[num].cnt++;
n/=i;
}
num++; //不同质因子个数加1
}
}
if(n==1) break; //及时推出循环
}
if(n!=1){ //无法被根号n以内的质因子除尽
fac[num].x=n; //必有一个大于根号n(即n本身)的质因子
fac[num++].cnt=1;
}
cout<<temp<<"=";
for(int i=0;i<num;i++){
cout<<fac[i].x;
if(fac[i].cnt!=1) cout<<"^"<<fac[i].cnt;
if(i<num-1)cout<<"*";
}
return 0;
}
发表于 2018-02-22 01:15:47
回复(0)
#include<stdio.h>
int main()
{
long long n;
while( scanf("%lld",&n)!= EOF )
{
printf("%lld=",n);
if( n == 1 )
printf("1");
int count = 0;
//如果i是非素数则一定不会被整除,count记录幂次数
for( long long i = 2 ; i * i <= n ; i++ )
{
while( n % i == 0 )
{
count++;
n = n / i;
}
if( count == 1 )
printf("%lld",i);
else if( count == 0 )
continue;
else
printf("%lld^%d",i,count);
count = 0;
if( n != 1 )
printf("*");
}
//循环最后的情况要么n = 1，说明最大的素因子幂次超过1
//要么 n 为一个素数，该素数也是最大的素因子且幂次数为1
if( n != 1 )
printf("%lld",n);
printf("\n");
}
return 0;
}
编辑于 2019-09-09 11:36:55
回复(0)
该题主要注意以空间换时间，利用sqrt化解多余的素数遍历。注意对于大素数因子可以直接判断是否为除剩下的被除数本身。
//prime factors
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
vector<int> prime;
int amount[100000000]={0};
bool is_prime(int n){
bool flag=1;
int n2=sqrt(n)+1;
for(int i=2;i<n2;i++){
if(n%i==0)flag=0;
}
return flag;
}
void get_prime_factor(int n){
int cnt=2;
while(n!=1&&cnt<=n){
if(is_prime(n)){
prime.push_back(n);
amount[n]++;
return;
}
if(is_prime(cnt)&&n%cnt==0){
prime.push_back(cnt);
amount[cnt]++;
n/=cnt;
while(n%cnt==0){
amount[cnt]++;
n/=cnt;
}
cnt=2;
}
else cnt++;
}
}
int main(){
int n;
cin>>n;
if(is_prime(n)){
cout<<n<<"="<<n;
return 0;
}
get_prime_factor(n);
cout<<n<<"="<<prime[0];
if(amount[prime[0]]>1)cout<<"^"<<amount[prime[0]];
for(int i=1;i<prime.size();i++){
cout<<"*"<<prime[i];if(amount[prime[i]]>1)cout<<"^"<<amount[prime[i]];
}
return 0;
}
发表于 2021-08-14 00:58:29
回复(0)
//数学知识背景：可能有大于sqrt(N)的质因数（指数必为1）
#include <iostream>
#include <math.h>
#include <map>
using namespace std;
#define MAX 1500000
long int N;
int p[MAX], k[MAX]; int cnt = 1;
map<int, int> fac2index;
bool isPrime(int x) {
if (x == 2)return true;
if (x % 2 == 0)return false;
for (int i = 3; i <= sqrt(x); i += 2) {
if (x % i == 0)return false;
}
return true;
}
void updateFac(int x) {
if (!fac2index[x]) {
p[cnt] = x; k[cnt] = 1;
fac2index[x] = cnt++;
}
else ++k[fac2index[x]];
}
int main()
{
cin >> N; int rem = N;
for (int i = 2; i <= sqrt(rem);) {
if (rem % i == 0 && isPrime(i)) {
updateFac(i);
rem /= i;
}
else ++i;
}
if (rem != 1) updateFac(rem);
//数学知识背景：可能有大于sqrt(N)的质因数（此时其指数必为1）
cout << N << "=";
if (N == 1)cout << 1;
else if (cnt == 1)cout << N;
else for (int i = 1; i < cnt; ++i) {
cout << p[i]; if (k[i] > 1)cout << "^" << k[i];
if (i < cnt - 1)cout << "*";
}
return 0;
}
发表于 2021-01-19 03:32:26
回复(0)
#include<iostream>
using namespace std;
struct factor{
int x,cnt;
}fac[10];
bool isprime(int n){
for(int i=2;i*i<n;i++)
if(n%i == 0) return false;
return true;
}
int main(){
long long int n;
cin >> n;
cout << n << "=";
int num = 0;
if(n==1) cout << n;
else{
for(int i=2;i*i<n;i++){
if(isprime(i) && n % i == 0){
fac[num].x = i;
fac[num].cnt = 0;
while(n % i == 0){
fac[num].cnt++;
n /= i;
}
num++;
}
}
if(n!=1) {
fac[num].x = n;
fac[num++].cnt = 1;
}
for(int i=0;i<num;i++){
cout << fac[i].x;
if(fac[i].cnt!=1) cout << "^" << fac[i].cnt;
if(i!=num-1) cout << "*";
}
}
return 0;
}
发表于 2020-08-11 18:14:02
回复(0)
#include <bits/stdc++.h>
using namespace std;
map<int, int> prime_cnt;
void solution(int n)
{
for (int i = 2; i <= sqrt(n); i++)
{
int cnt = 0;
while (n % i == 0)
{
cnt++;
n /= i;
}
if(cnt != 0)
prime_cnt[i] = cnt;
}
if (n != 1)
prime_cnt[n] = 1;
}
int main()
{
int N;
cin >> N;
if (N == 1)
prime_cnt[1] = 1;
else
solution(N);
cout << N << "=";
for (auto p : prime_cnt)
{
if (p.first != prime_cnt.begin()->first)
cout << "*";
cout << p.first;
if (p.second != 1)
cout << "^" << p.second;
}
cout << endl;
}
发表于 2020-03-30 18:41:11
回复(0)
//思路：唯一分解定理裸题。注意几个坑点：当输入为1，输入为素数。
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
typedef long long LL;
LL n;int vis[maxn];
vector<int> primes;
map<int,int> mp;
void init(){
int m=sqrt(1e6-100);
for(int i=2;i<=m;++i)
if(!vis[i]){
for(int j=i*i;j<=maxn-10;j+=i)
vis[j]=1;
}
for(int i=2;i<=maxn-10;++i)
if(!vis[i]) primes.push_back(i);
}
int main(){
init();//cout<<primes.front()<<endl;
scanf("%lld",&n);printf("%lld=",n);
LL tmp=n;
if(n==1) printf("1"),exit(0);
for(auto it=primes.begin();it!=primes.end();++it){
while(n%(*it)==0)
++mp[*it],n/=(*it);
if(n==1) break;
}
//cout<<"****"<<endl<<mp[2]<<endl;
if(n==tmp) printf("%lld",n),exit(0);
if(n!=1) ++mp[n];
int ok=1;
for(auto &ch:mp){
if(ok){
ok=0;
if(ch.second==1) printf("%d",ch.first);
else printf("%d^%d",ch.first,ch.second);
}else{
if(ch.second==1) printf("*%d",ch.first);
else printf("*%d^%d",ch.first,ch.second);
}
}
return 0;
}
发表于 2018-03-04 16:12:24
回复(0)
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
bool isPrime(int n)
{ if(n<=1) return false; if(n==2) return true; for(int i=2;i<=sqrt(n);i++) if(n%i==0) return false; return true;
}
int main()
{ int n,t,x=0; int a[30],b[30]; cin>>n; t = n; if(n==1) cout<<"1=1"; else{ int sqr = sqrt(n); for(int i=2;i<=sqr&&n>1;i++) { if(isPrime(i)) if(n%i==0) { a[x] = i; b[x] = 0; while(n%i==0) { b[x]++; n /= i; } x++; } } if(n!=1) { a[x] = n; b[x++] = 1; } cout<<t<<"="; for(int i=0;i<x;i++) { cout<<a[i]; if(b[i]!=1) cout<<"^"<<b[i]; if(i<x-1) cout<<"*"; } } return 0;
}
发表于 2018-02-24 01:21:31
回复(0)
import java.util.Scanner;
import java.util.ArrayList;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
System.out.print(n+"=");
if(n==1||isPrime(n)){
System.out.println(n);
return;
}
int prime = 2;
ArrayList<Integer> list1 = new ArrayList<Integer>();
ArrayList<Integer> list2 = new ArrayList<Integer>();
while(n!=1){
if(n%prime==0){
n /= prime;
if(list1.isEmpty()||list1.get(list1.size()-1)!=prime){
list1.add(prime);
list2.add(1);
}else if(list1.get(list1.size()-1)==prime){
list2.set(list2.size()-1,list2.get(list2.size()-1)+1);
}
}else if(isPrime(n)){
list1.add(n);
list2.add(1);
break;
}else{
prime = next(prime);
}
}
for(int j = 0;j<list1.size();j++){
System.out.print(list1.get(j));
if(list2.get(j)>1)
System.out.print("^"+list2.get(j));
if(j+1!=list1.size())
System.out.print("*");
}
}
private static boolean isPrime(int a){
int limit = (int)Math.sqrt(a);
for(int i = 2;i<=limit;i++)
if(a%i==0)
return false;
return true;
}
private static int next(int p){
p++;
while(!isPrime(p))
p++;
return p;
}
}
发表于 2016-07-18 16:39:37
回复(0)
解题思路：
本题是正整数n的素因子分解问题。n分为3种情况：
（1）n=1，特殊数据，直接按指定格式输出即可。
（2）n是素数，不用分解，直接按指定格式输出即可。要判别n是否为素数，有多种方法，对于本题而言，最简单的方法是使用试商法。因为即使对于n=2147483647=2^31-1范围内的整数，用试商法效率也是很高的，具体参见下面给出的代码。
（3）n是大于1的非素数，这正是本题要完成的工作。可以从最小的素数2开始，依次用2,3,4，5，...,sqrt(n)对n进行分解。当然，如果n很大，对n开平方根后其值也较大，这样循环检测的话，很可能造成程序超时，因为用了一些非素数如4、6、8...等等。当然，可以考虑采用筛法，事先把一定范围内的素数全部筛选出来，存入数组，然后只用这些素数去分解n，效率会相应提高很多。对于本题而言，如果考虑到哪些初学程序设计的同学，因为数组的知识一般在教学过程中比较靠后，所以采用了没有使用数组的方式来完成。参见下面的代码： for(i=2; i<=k; i++) //从最小的素数2开始对n进行分解
{
int tot=0; //某个素因子出现的次数(幂指数)
if(n%i==0) //i是素因子
{
while(n%i==0)//对n进行分解
{
tot++; //累计素因子出现的次数
n/=i; //对n进行分解
}
//按指定格式打印
...........
}
k=(int)sqrt(n+0.0); //更新k的值，这是本题的关键之处 }
（4）本题还有一点需要注意，即打印的格式。详细解释参见下面的完整代码：
#include<iostream>
#include<cmath>
using namespace std;
//朴素试商法判别n是否为素数
bool is_prime(int n)
{
if(n<2)return false;
int k=(int)sqrt(n+0.0);
for(int i=2; i<=k; i++)
if(n%i==0)return false;
return true;
}
int main()
{
int n;
while(cin>>n)//循环输入,处理多组数据
{
cout<<n<<"=";
if(n==1) //处理特殊数据
{
cout<<1<<endl;
continue;
}
if(is_prime(n)) //处理素数(不可再分解)
{
cout<<n<<endl;
continue;
}
int i,k=(int)sqrt(n+0.0);//n的素因子不可能超过k
bool first=true;
for(i=2; i<=k; i++) //从最小的素数2开始对n进行分解
{
int tot=0; //某个素因子出现的次数(幂指数)
if(n%i==0) //i是素因子
{
while(n%i==0)//对n进行分解
{
tot++; //累计素因子出现的次数
n/=i; //对n进行分解
}
if(first) //处理n的第1个素因子,按p1^k1的格式打印
{
first=false;
if(tot>=2)cout<<i<<"^"<<tot;//按幂指数方式打印
else cout<<i; //素因子只出现1次,直接打印该素因子
}
else //从第2个素因子开始,按*p2^k2的格式打印
{
if(tot>=2)cout<<"*"<<i<<"^"<<tot;
else cout<<"*"<<i;
}
}
//某个素因子不能分解n后得到的新的n,新的n的素因子不可能超过k
//这是本题的关键之处,即每得到一个新的n,均对其开平方根,否则会超时
k=(int)sqrt(n+0.0);
}
if(n>1)cout<<"*"<<n; //输出最后一个素因子
cout<<endl; //多组数据之间换行
}
return 0;
}
发表于 2015-08-09 21:07:03
回复(0)
#include<bits/stdc++.h>
using namespace std;
const int Max=1e5;
int prime[Max],num=0;
bool a[Max]= {0};
struct factor {
int x;
int y;
} fac[10];
void f() {
for(int i=2; i<Max; i++) {
if(!a[i]) {
prime[num++]=i;
}
for(int j=2*i; j<Max; j+=i) {
a[j]=1;
}
}
}
int main() {
f();
int n,x=0;
while(cin>>n) {
int t=n;
if(n==1) {
cout<<"1=1"<<endl;
} else {
int m=(int)sqrt(1.0*n);
for(int i=0; i<num&&prime[i]<=m; i++) {
if(n%prime[i]==0) {
fac[x].x=prime[i];
fac[x].y=0;
while(n%prime[i]==0) {
fac[x].y++;
n/=prime[i];
}
x++;
}
if(n==1) break;
}
if(n!=1) {
fac[x].x=n;
fac[x++].y=1;
}
cout<<t<<"=";
for(int i=0; i<x; i++) {
if(fac[i].y==1) {
cout<<fac[i].x;
} else {
cout<<fac[i].x<<'^'<<fac[i].y;
}
if(i!=x-1) {
cout<<'*';
}
}
}
}
return 0;
}
using namespace std;
const int Max=1e5;
int prime[Max],num=0;
bool a[Max]= {0};
struct factor {
int x;
int y;
} fac[10];
void f() {
for(int i=2; i<Max; i++) {
if(!a[i]) {
prime[num++]=i;
}
for(int j=2*i; j<Max; j+=i) {
a[j]=1;
}
}
}
int main() {
f();
int n,x=0;
while(cin>>n) {
int t=n;
if(n==1) {
cout<<"1=1"<<endl;
} else {
int m=(int)sqrt(1.0*n);
for(int i=0; i<num&&prime[i]<=m; i++) {
if(n%prime[i]==0) {
fac[x].x=prime[i];
fac[x].y=0;
while(n%prime[i]==0) {
fac[x].y++;
n/=prime[i];
}
x++;
}
if(n==1) break;
}
if(n!=1) {
fac[x].x=n;
fac[x++].y=1;
}
cout<<t<<"=";
for(int i=0; i<x; i++) {
if(fac[i].y==1) {
cout<<fac[i].x;
} else {
cout<<fac[i].x<<'^'<<fac[i].y;
}
if(i!=x-1) {
cout<<'*';
}
}
}
}
return 0;
}
发表于 2022-10-23 11:46:07
回复(1)
直接计数就可为什么这题通过率可以这么低？？？
更多PAT甲级题解---acking-you.github.io
题目
题目详解
直接看例子就知道了，就是把N进行质因数分解，然后注意的是有多个相同的质因数时需要把它们以指数形式输出。
- 感觉算是入门的的水题了，咋通过率这么低。。。。
代码详解
记录质因数次数的方式
- 用哈希表的形式进行记录(也可用数组进行记录，此处用了STL的散列表)
unordered_map<int, int> cnt; //记录质因数的次数 vector<int> num; //记录所有质因数
- 同时将指数和次数形成映射(实际用之前的STL的哈希表就能实现)
当然你也可以用自己的结构体实现相应的映射。
此时为保证输出有序，应使用map而不是unordered版本。
map<int, int> cnt; //记录质因数和次数的映射关系
预处理过程--判断质数和更新数据
bool isPrime(long x) {
for (int i = 2; i * i <= x; i++) {
if (x % i == 0) return false;
}
return true;
}
void solve() {
ios::sync_with_stdio(false);
cin >> N;
cout << N << "=";
if (isPrime(N)) {
cout << N;
return;
}
int t = N;
for (int i = 2; i <= N; i++) {
if (t % i == 0) {
while (t % i == 0) {
cnt[i]++;
t /= i;
}
}
if (t == 1) {
break;
}
}
} 输出过程处理--将每个元素看作单独处理
void handle_one(int a) { //处理单个元素的打印
cout << a;
switch (cnt[a]) {
case 1:
break;
default:
cout << '^' << cnt[a];
}
}
void print() {
if (cnt.empty())
return;
for (auto it = cnt.begin(); it != cnt.end(); ) {
handle_one(it->first);
it++;
if (it != cnt.end())
cout << "*";
}
}
代码提交
两者的效率都差不多，想要进一步提高效率，还是得用原生数组，或者是直接记录。
#include<bits/stdc++.h>
using namespace std;
long N;
map<int, int> cnt; //记录质因数和次数的映射关系
bool isPrime(long x) {
for (int i = 2; i * i <= x; i++) {
if (x % i == 0) return false;
}
return true;
}
void solve() {
ios::sync_with_stdio(false);
cin >> N;
cout << N << "=";
if (isPrime(N)) {
cout << N;
return;
}
int t = N;
for (int i = 2; i <= N; i++) {
if (t % i == 0) {
while (t % i == 0) {
cnt[i]++;
t /= i;
}
}
if (t == 1) {
break;
}
}
}
void handle_one(int a) { //处理单个元素的打印
cout << a;
switch (cnt[a]) {
case 1:
break;
default:
cout << '^' << cnt[a];
}
}
void print() {
if (cnt.empty())
return;
for (auto it = cnt.begin(); it != cnt.end(); ) {
handle_one(it->first);
it++;
if (it != cnt.end())
cout << "*";
}
}
int main() {
solve();
print();
return 0;
}
发表于 2021-10-02 15:58:45
回复(0)
#include<bits/stdc++.h>
using namespace std;
int main(){
int m;
int flag=0;
while(cin>>m){
// int count=0;
if(m==1){
cout<<"1=1"<<endl;
continue;
}
cout<<m<<"=";
for(int j=2;j*j<=m;j++){
if(m%j==0){
flag++;
if(flag==1){
cout<<j;
}
else cout<<"*"<<j;
}
int count=0;
while(m%j==0){
m=m/j;
count++;
}
if(count>1){
cout<<"^"<<count;
}
if(m<=1) break;
}
if(m!=1&&flag!=0){
cout<<"*"<<m;
}else if(m!=1&&flag==0){
cout<<m;
}
cout<<endl;
}
} 思路很简单，就是输出格式上坑了几次
编辑于 2020-03-20 22:32:36
回复(1)
人生苦短，我用map,这道题c++用map可以大大简化c++代码量，思路还清晰。本题坑点在于n=1时要输出1=1,不等于1就用质因数线性筛分解法做即可
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
while(~scanf("%d",&n)){
map<int,int> mp;
int temp=n;
if(n==1)printf("1=1");
else{
for(int i=2;i<sqrt(n);i++){
if(n%i==0){
while(n%i==0){
mp[i]++;
n/=i;
}
}
}
if(n!=1)mp[n]++;
printf("%d=",temp);
int count=0;
for(map<int,int>::iterator it=mp.begin();it!=mp.end();it++){
if(it->second>1){
printf("%d^%d",it->first,it->second);
}else if(it->second==1){
printf("%d",it->first);
}
count++;
if(count!=mp.size()){
printf("*");
}else{
printf("\n");
}
}
}
}
return 0;
}
发表于 2020-03-13 10:03:51
回复(0)
题目说了一个长整型，我就有点迷，这个long 按照道理来说，64位机是64位，那么大概就是10的19次方这么大，如果要找质数的话，找不到这么大的数组，要用其它办法。最后我用个int它也行，说明是32位的，测试用例最大貌似也才10^8,再开个方就是10^4-10^5，这就可以用筛法来存质数进而判断，不知道这样理解正不正确，可能服务器是32位机？，有错误请大神指点出来
#include<iostream>
(720)#include<vector>
#include<limits.h>
(1124)#include<cmath>
using namespace std;
const int MAXN = 1e6;
bool prime[MAXN];
vector<int>primeFactors;
vector<int>indexofPrime;
void getPrime() {
prime[0] = false;
prime[1] = false;
for (int i = 2; i < MAXN; i++) {
if (!prime[i]) { continue; }
for (int j = i * i; j < MAXN; j += i) {
prime[j] = false;
}
}
}
int main() {
fill(prime, prime + MAXN, true);
getPrime();
int n;
cin >> n;
int up = sqrt(n);
int tmp = n;
for (int i = 2; i < MAXN; i++) {
if (prime[i]) {
int num = 0;
while (tmp % i == 0) {
num++;
tmp /= i;
}
if (num != 0) {
primeFactors.push_back(i);
indexofPrime.push_back(num);
}
}
if (tmp == 1) { break; }
}
printf("%d=", n);
for (int i = 0; i < primeFactors.size(); i++) {
if (i) printf("*");
printf("%d", primeFactors[i]);
if(indexofPrime[i]!=1){
printf("^%d",indexofPrime[i]);
}
}
if (primeFactors.empty()){printf("%d", n);}//n本身是一个质数
if(!primeFactors.empty()&&tmp!=1){//n分解后还存在一个大于1e6的质数
printf("*%d",tmp);
}
}
发表于 2020-02-29 13:05:17
回复(0)
a = int(input())
d = {};m = [];b = a
while True:
for i in range(2,int(a ** 0.5) + 1):
if a / i == a // i:
a /= i
d[i] = d[i] + 1 if i in d else 1
break
else:
d[int(a)] = d[int(a)] + 1 if int(a) in d else 1
break
for i in sorted(d):
m.append((str(i) + '^' + str(d[i])) if d[i] > 1 else str(i))
print(str(b) + '=' + '*'.join(m))
发表于 2020-02-19 14:33:01
回复(0)
/*
改了很多次才通过，代码显得很凌乱
一开始的只是简单的穷举，提交后超时，所以改成了这种方法
我的思路是这样：
伪代码：
cin>>n;
for i to sqrt(n):
if i 是素数：
存入结果i，i次数为1
n=n/i
while n%i==0:
i次数+1
n/=i
最后n要么是1，要么是一个素数
n=1有两种情况：1.输入的即是1；2.连除后得到1
前一种情况按照要求输出1即可
若n不为1，即n为素数，则结果中加入n即可
代码没有整理，看了一下评论，后面有一位‘巴黎的夜雪’的代码思路和我一样，且更简洁易懂，若有兴趣的看他的即可
*/
#include<iostream>
using namespace std;
int main() {
long N;
while (cin >> N) {
long n = N;
int num = 0;
long prime[50]; //long int小于2^31，大于31即不会越界
int amount[50];
int num2 = 0;
for (long i = 2; i * i <= n; i++) {
if (n%i == 0) {
bool istrue = true;
for (long j = 2; j <= long(sqrt(i)); j++) {
if (i%j == 0) {
istrue = false;
break;
}
}
if (istrue) {
prime[num] = i;
amount[num] = 1;
n = n / i;
while (true) {
if (n%i == 0) {
amount[num] += 1;
n = n / i;
}
else {
break;
}
}
num++;
}
num2++;
}
}
cout << N << "=";
if (num2==0||n!=1) {
prime[num] = n;
amount[num] = 1;
num++;
}
for (int i = 0; i < num - 1; i++) {
if (amount[i] > 1) {
cout << prime[i] << "^" << amount[i] << "*";
}
else {
cout << prime[i] << "*";
}
}
if (amount[num - 1] > 1) {
cout << prime[num - 1] << "^" << amount[num - 1];
}
else {
cout << prime[num - 1];
}
cout << endl;
}
return 0;
}
编辑于 2019-09-09 10:24:00
回复(0)
n = input()
n = int(n)
backup = int(n)
if n==1:
print('1=1')
else:
i = 2
lst,out = [],[]
while n>1:
if n%i==0:
lst.append(i)
n= n//i
else:
if i<=n**0.5:
i+=1
else:
i = int(n)
out = sorted(set(lst))
print(str(backup)+'=',end='')
for i in range(0,len(out)-1):
if lst.count(out[i])>1:
print(str(out[i])+'^'+str(lst.count(out[i]))+"*",end='')
else:
print(str(out[i])+"*",end='')
if lst.count(out[len(out)-1])>1:
print(str(out[len(out)-1])+'^'+str(lst.count(out[len(out)-1])))
else:
print(str(out[len(out)-1]))
发表于 2018-12-02 19:50:58
回复(0)
x=input()
p,q,n,i=[1],[1],int(x),2
while n!=1:
if n%i==0:
if i==p[-1]:
q[-1]+=1
else:
p.append(i)
q.append(1)
n/=i
else:
i=int(n) if i>n**0.5 else i+1
res=[] if int(x)!=1 else ['1']
for i in range(1,len(p)):
if q[i]==1:
res.append(str(p[i]))
else:
res.append(str(p[i])+'^'+str(q[i]))
print(x+'='+'*'.join(res))
发表于 2018-08-31 09:58:53
回复(0)
思路： 用map存储因子的个数。然后按照格式输出。
#include <iostream>
#include <map>
#include <math.h>
#include <fstream>
using namespace std;
#ifndef Debug
ifstream ifile("case.txt");
#define cin ifile
#endif
bool Prime(long long x)
{
bool check = true;
if (x == 2)
return check;
for (int i = 2; i <= sqrt(x); i++)
{
if (x % i == 0)
{
check = false;
break;
}
}
return check;
}
void GenMap(int n, map<int,int> & mp)
{
if (n == 1|| Prime(n))
{
mp[n]++;
return;
}
long long muti = 1;
for (int i = 2; i <=n; )
{
if (!Prime(i))
{
i++;
}
if (n % i == 0)// i是他的因子
{
n = n / i;
mp[i]++;
}
else
i++;
}
}
int main()
{
long long n;
cin >> n;
map<int,int> mp;
GenMap(n, mp);
cout << n << "=";
for (map<int, int>::iterator it = mp.begin(); it != mp.end(); it++)
{
if (it == mp.begin())
{
cout << it->first;
if (it->second > 1)
{
cout << "^" << it->second;
}
}
else
{
cout << "*" <<it->first;
if (it->second > 1)
{
cout << "^" << it->second;
}
}
}
system("pause");
}
发表于 2018-08-27 16:27:35
回复(0)
问题信息
难度：
27条回答
14收藏
6661浏览
通过挑战的用户
-
2023-03-11 13:37:08
-
2023-03-04 22:47:05 -
2023-02-27 15:33:08
-
2023-02-27 00:27:09 -
2023-02-24 14:39:34
相关试题
-
评论(3922) 来自华为研发工程师编程题
-
评论(3148)
-
评论(2565) 来自华为研发工程师编程题
-
评论(466)
-
评论(1)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
