分解质因数

妖狐艹你老母 2024-03-26 20:25 10阅读 0赞

## 分解质因数 ##

给定 n个正整数 ai，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。

输入格式

第一行包含整数 n。

接下来 n行，每行包含一个正整数 ai。

输出格式  
对于每个正整数 ai，按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。

每个正整数的质因数全部输出完毕后，输出一个空行。

数据范围  
1≤n≤100,  
2≤ai≤2×109  
输入样例：

2
    6
    8

输出样例：

2 1
    3 1
    
    2 3

**提交代码**

**C++**

#include<iostream>
    using namespace std;
    
    int divide(int n)
    {
        
        for (int i = 2; i <= n / i; ++ i)
        {
        
            int cnt = 0;
            if (n % i == 0)
            {
        
                while(n % i == 0)
                {
        
                    cnt ++;
                    n /= i;
                }
                cout << i << " " << cnt << endl;
            }
        }
        if (n != 1) cout << n << " " << 1 << endl;
        cout << endl;
    }
    int main()
    {
        
        int n;
        cin >> n;
        while(n --)
        {
        
            int t;
            cin >> t;
            divide(t);
        }
        return 0;
    }

**Java**  
重点是这个divide函数如何编写。

static void divide(int x)
        {
        
            for (int i = 2; i <= x / i; ++ i)
            {
        
                int cnt = 0;
                if (x % i == 0)
                {
        
                    while(x % i == 0)
                    {
        
                        cnt ++;
                        x /= i;
                    }
                    System.out.println(i + " " + cnt);
                }
            }
            if (x != 1) System.out.println(x + " " + 1);
            System.out.println();
        }

import java.io.*;
    
    public class Main
    {
        
        static void divide(int x)
        {
        
            for (int i = 2; i <= x / i; ++ i)
            {
        
                int cnt = 0;
                if (x % i == 0)
                {
        
                    while(x % i == 0)
                    {
        
                        cnt ++;
                        x /= i;
                    }
                    System.out.println(i + " " + cnt);
                }
            }
            if (x != 1) System.out.println(x + " " + 1);
            System.out.println();
        }
        public static void main(String [] args) throws IOException
        {
        
            BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
            int n = Integer.parseInt(reader.readLine());
            while(n -- > 0)
            {
        
                int t = Integer.parseInt(reader.readLine());
                divide(t);
            }
        }
    }