2022 年 11 月 16 日

C, C++, Python, ZJ解題

a010: 因數分解

2022.11.16 PM 04:30 by CBJ

來源 : https://zerojudge.tw/ShowProblem?problemid=a010
出題者 : Zerojudge
標籤 : 數論(質因數分解)
難易度 : 3

解題想法 : 
此處將輸入的整數定義為n。

for迴圈i從2開始跑到一個定義的無限大值，終止條件為n已經是1(分解完畢)時。(不須額外處理非質因數的問題，因為遇到非質因數時，什麼事也不會做(每個非質因數都可以被它之前的質因數分解，所以在做因數分解時不會出現非質因數))

起初設定cnt為0，表示i使用到的次數。

for內有一個while，只要n%i==0表示可以整除，則將次數+1，並把n除以i繼續迴圈。

每次離開while以後檢查cnt，若大於0(表示有使用到)則儲存到ans陣列(每個元素皆為兩個值:i和cnt)

最後跑一個for迴圈i從0~(ans的大小)，若不為第1個(i!=0)則要先在前面輸出" * "，然後取出ans[i]中的第1個元素為n，第2個元素為cnt，若cnt>1則還要輸出次方，因此可以用if...else語法完成這件事。

(記得最後要輸出一個換行。)

//C language
//solution link(含註解): https://github.com/CBJ0519/CBJsProgramDiary.com/blob/main/zj/a010.c

#include<stdio.h>
int main(){
    int n;
    scanf("%d",&n);
    int tmp[100000][2];
    int index=0,tmp_size=0;
    for(int i=2;i<1e9;i++){
        if(n==1) break;
        int cnt=0;
        while((n%i)==0){
            cnt++;
            n/=i;
        }
        if(cnt){
            tmp[index][0]=i;
            tmp[index][1]=cnt;
            index++;
            tmp_size++;
        }
    }
    for(int i=0;i<tmp_size;i++){
        if(i){
            printf(" * ");
        }
        int n=tmp[i][0];
        int cnt=tmp[i][1];
        if(cnt>1){
            printf("%d^%d",n,cnt);
        }
        else{
            printf("%d",n);
        }
    }
    printf("\n");
    return 0;
}

//C++ language
//solution link(含註解): https://github.com/CBJ0519/CBJsProgramDiary.com/blob/main/zj/a010.cpp

#include<iostream>
#include<vector>
#include<utility>
#include<string>
using namespace std;
int main(){
    int n; cin>>n;
    vector<pair<int,int>>tmp;
    for(int i=2;i<1e9;i++){
        if(n==1) break;
        int cnt=0;
        while(not (n%i)){
            cnt++;
            n/=i;
        }
        if(cnt){
            tmp.push_back({i,cnt});
        }
    }
    for(int i=0;i<tmp.size();i++){
        if(i) cout<<" * ";
        int n=tmp[i].first;
        int cnt=tmp[i].second;
        if(cnt>1){
            cout<<n<<"^"<<cnt;
        }
        else{
            cout<<n;
        }
    }
    cout<<"\n";
    return 0;
}

## Python language
## solution link(含註解): https://github.com/CBJ0519/CBJsProgramDiary.com/blob/main/zj/a010.py

n=int(input())
tmp=[]
for i in range(2,int(1e9)):
    if n==1: break
    cnt=0
    while not n%i:
        cnt+=1
        n//=i
    if cnt: tmp.append([i,cnt])
ans=[]
for i,cnt in tmp:
    if cnt>1: ans.append(f'{i}^{cnt}')
    else: ans.append(i)
print(*ans,sep=' * ')

相關文章

發佈留言取消回覆