import java.util.Scanner; public class Main {

public static void main(String[] args) {
    Scanner input = new Scanner(System.in);
    int T = input.nextInt();
    while(T>0){
        //求最大公因数的和
        int n = input.nextInt();
        int[] arr = new int[n];//0代表没用过，1代表用过
        for(int i=1;i<=n;i++){
            arr[i-1] = i;
        }
        int b;
        int sum = 0;
        int count = n;
        while(true){
            int maxi=-1,maxj=-1;
            int maxgcd = 0;

            //找出公因数最大的i,j
            for(int i=0;i<count;i++){
                for(int j=i+1;j<count;j++){
                    if(sp(arr[i],arr[j])>maxgcd){
                        maxgcd = sp(arr[i],arr[j]);
                        maxi = i;
                        maxj = j;
                    }
                }
            }
            //更换数据
            arr[maxi] = maxgcd;
            arr[maxj] = arr[count-1];
            sum+=maxgcd;
            count--;
            //数堆只剩下一个数，结束循环
            if(count==1){
                break;
            }

        }
        System.out.println(sum);
        T--;
    }

}

public static int sp(int a,int b){
    int min;
    int max = 1;
        if(a<b){
            min=a;
        }else{
            min=b;
        }
        for(int i = 2;i<=min;i++){
            if(a%i==0&&b%i==0){
                max = i;
            }
        }
    return max;
}

}

我这个时间复杂度是O(n^3)，感觉优化应该从找具有最大公约数的两个数下手，或者是退出while循环下手

我 20 年 10 月时交的代码：

#include <iostream>
using namespace std;
int gcds[10005];
int sum[10005];//python求得最大值16507015没有爆int
int req[25];//用于max比较了，就不可以用short
int main()
{
    int n, maxreq=0, i,j;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>req[i];
        maxreq=max(maxreq, req[i]);
    }
    //cout<<maxreq;
    for(i=2;i<=maxreq;i++)
    {
        //found=0;
        for(j=i-1;j>1;j--)
        {
            if(i%j==0) break;
        }
        //cout<<i<<" "<<j<<endl;
        gcds[i]=j;
        sum[i]=gcds[i]+sum[i-1];
    }
    for(i=0;i<n;i++) cout<<sum[req[i]]<<endl;
    return 0;
}