Codility每周一课：L10 Prime and compo

0.png

P10.1 CountFactors

Count factors of given number n.

• P10.1 因子个数
  计算数n的因子个数

正整数D是正整数N的一个因子，如果存在一个整数M，使得N=D*M。

例如，6是24的因子，因为M=4满足上述条件（24=6*4）。

编写函数：

def solution(N)

给定一个正整数N，则返回其因子的个数。

例如，如果N=24，函数应该返回8，因为24有8个因子，即1、2、3、4、6、8、12、24。

假定：

1. N是区间[1，2147483647]内的整数；

• 解题思路

不用遍历所有的小于Ｎ的数，只要遍历不小于Ｎ的平方根的数即可。因为每次遍历都可以获得２个因子。

• Python3代码

# -*- coding：utf-8 -*-
# &Author  AnFany
# Lesson 10：Prime and composite numbers
# P 10.1 CountFactors


def solution(N):
    """
    返回N的所有因子的个数,时间复杂度O(sqrt(N))
    :param N: 正整数N
    :return: 返回N的所有因子的个数
    """
    factor_dict = {}
    for i in range(1, int(N ** 0.5) + 1):
        if N % i == 0:
            if i not in factor_dict:
                factor_dict[i] = 0
            j = N / i
            if j == int(j) and j not  in factor_dict:
                factor_dict[j] = 0
    return len(factor_dict)

• 结果

image

点击获得更多编程练习题。欢迎Follow，感谢Star!!! 扫描关注微信公众号pythonfan，获取更多。

image image