分解质因数

从小到大枚举所有数。

for ( int i = 2; i <= n; i ++ )
    if ( n % i == 0 ) // i 一定是质数
    {
        // 求i的次数
        int s = 0;
        while ( n % i == 0 ) n /= i, s ++;
        printf("%d %d\n", i, s);
    }
puts("");

$n$ 中，最多只会包含一个大于 $\sqrt{n}$ 的质因子。分解完成后，单独处理一下 $n$ 即可。

for ( int i = 2; i <= n / i; i ++ )
    if ( n % i == 0 ) // i 一定是质数
    {
        // 求i的次数
        int s = 0;
        while ( n % i == 0 ) n /= i, s ++;
        printf("%d %d\n", i, s);
    }
if ( n > 1 ) prinf("%d %d", n, 1);
puts("");

题目描述

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

输入格式

第一行包含整数 $n$。

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

输出格式

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

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

数据范围

$1≤n≤100$,
$1≤a_i≤2×10^9$

样例

输入样例：

2
6
8

输出样例：

2 1
3 1

2 3

代码

暴力版 $O(n)$

C++

#include <iostream>

using namespace std;

void worker(int n)
{
    for ( int i = 2; i <= n; i ++ )
        if ( n % i == 0 )
        {
            int s = 0;
            while ( n % i == 0 ) n /= i, s ++;
            printf("%d %d\n", i, s);
        }
    puts("");
}

int main()
{
    int T;
    cin >> T;
    while ( T -- )
    {
        int n;
        cin >> n;
        worker(n);
    }
    return 0;
}

Java

import java.util.*;

public class Main
{
    private static Scanner in = new Scanner(System.in);
    
    public static void main(String args[])
    {
        int T = in.nextInt();
        while ( T -- > 0 ) worker(in.nextInt());
    }
    
    private static void worker(int n)
    {
        for ( int i = 2; i <= n; i ++ )
            if ( n % i == 0 )
            {
                int s = 0;
                while ( n % i == 0 )
                {
                    n /= i;
                    s ++;
                }
                System.out.printf("%d %d\n", i, s);
            }
        System.out.printf("\n");
    }
}

优化版 $O(\sqrt{n})$

C++

#include <iostream>

using namespace std;

void woker(int n)
{
    for ( int i = 2; i <= n / i; i ++ )
        if ( n % i == 0 )
        {
            int s = 0;
            while ( n % i == 0 ) n /= i, s ++;
            printf("%d %d\n", i, s);
        }
    if ( n > 1 ) printf("%d %d\n", n, 1);
    puts("");
}

int main()
{
    int T;
    cin >> T;
    while ( T -- )
    {
        int n;
        cin >> n;
        woker(n);
    }
    return 0;
}

Java

import java.util.*;

public class Main
{
    private static Scanner in = new Scanner(System.in);
    
    public static void main(String args[])
    {
        int T = in.nextInt();
        while ( T -- > 0 ) worker(in.nextInt());
    }
    
    private static void worker(int n)
    {
        for ( int i = 2; i <= n / i; i ++ )
            if ( n % i == 0 )
            {
                int s = 0;
                while ( n % i == 0 )
                {
                    n /= i;
                    s ++;
                }
                System.out.printf("%d %d\n", i, s);
            }
        if ( n > 1 ) System.out.printf("%d %d\n", n, 1);
        System.out.printf("\n");
    }
}