题解 | #求int型正整数在内存中存储时1的个数#

思路

这道题第一次见到的时候发现解法可以很暴力。

Java版本代码

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
    public static List<Integer> revert(int num) {
        List<Integer> list = new ArrayList<>();
        for (int i = 2; i <= num; i++) {
            if (num % i == 0) {
                list.add(i);
                num /= i;
                i--;
            }
        }
        if (list.isEmpty()) {
            list.add(num);
        }
        return list;
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            List<Integer> list = revert(a);
            list.forEach(integer -> System.out.print(integer + " "));
        }
    }
}

就是从2开始反复的去除输入的数字，发现可以整除就输出。这种解法的好处就是简单，但是坏处也很明显，就是特别慢，我的这段代码的执行时间已经达到了3259ms，基本快超时了。

继续审视这道题，发现这其实是判断素数的一个变种。

我们知道，如果一个数不是素数，那么这个数字一定会有至少一个因子小于sqrt(number)，另外会有一个因子大于sqrt(number)，根据这个原理改造一下代码：

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static List<Integer> revert(int num) {
        List<Integer> list = new ArrayList<>();
        int end = (int) Math.sqrt(num);
        for (int i = 2; i <= end; i++) {
            while (num % i == 0) {
                list.add(i);
                num /= i;
            }
            if (num == 1) {
                break;
            }
        }
        // 这一句负责找到那个大于num平方根的因子
        if (num != 1) {
            list.add(num);
        }
        if (list.isEmpty()) {
            list.add(num);
        }
        return list;
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            List<Integer> list = revert(a);
            list.forEach(integer -> System.out.print(integer + " "));
        }
    }
}

这一段代码的执行时间就只有185ms了。

另外还是要感叹C语言的效率，同样的算法，执行只需要3ms：

#include <stdio.h>
#include <math.h>

int main(void)
{
    int num;
    scanf("%d", &num);
    int end = (int) sqrt(num);
    for (int i = 2; i <= end; i++)
    {
        while (num % i == 0)
        {
            printf("%d ", i);
            num /= i;
        }
        if (num == 1)
        {
            break;
        }
    }
    if (num != 1) 
    {
        printf("%d ", num);
    }
    return 0;
}