每周一课：L11 Sieve of Eratosthenes(1

11.png

P11. 1 CountNonDivisible

Calculate the number of elements of an array that are not divisors of each element.

P11. 1 非因子数
计算一个数组中所有元素的非因子数的个数

由N个整数组成的数组A。对于每个数A[i]，其中0≤i<N，要计算数组A中不是A[i]因子的元素数。并称这些元素为非因子数。

例如，整数N=5时的数组A：
A[0]=3，A[1]=1，A[2]=2，A[3]=3，A[4]=6

对于以下元素：
a[0]=3，非因子数为：2，6，个数为2；
a[1]=1，非因子数为：3，2，3，6，个数为4；
a[2]=2，非因子数为：3，3，6，个数为3；
a[3]=3，非因子数为：2，6，个数为2；
A[4]=6，没有任何非因子数，个数为0；

编写函数：

def solution(A)

给定一个由N个整数组成的数组A，则返回表示非因子数个数的序列。例如，针对上面的示例，函数应该返回[2，4，3，2，0]。

假定：

1. N是区间[1，50000]内的整数；
2. 数组A的每个元素都是区间[1，2*N]内的整数；

• 解题思路

首先得到数组A中各个元素出现的次数字典。然后遍历数组A，对于每一个元素j，在从1到sqrt(j)+1中寻找j的因子，一次遍历可以获得2个(如果为平方根，则就只有一个)因子。如果因子在次数字典里，则加上其出现的次数。最后A的长度减去总的次数即可。并且要用字典存储已经获得非因子个数值的数，为了减少后面的重复的运算。

• Python3代码

# -*- coding：utf-8 -*-
# &Author  AnFany
# Lesson 11：Sieve of Eratosthenes
# P 11.1 CountNonDivisible


def solution(A):
    """
    针对数组中的每一个元素，得到数组A中不是其因子数的个数, 时间复杂度O(N * log(N))
    :param A: 数组A
    :return: 返回每个元素的非因子数的个数序列
    """
    element_dict = {}
    for i in A:
        if i in element_dict:
            element_dict[i] += 1
        else:
            element_dict[i] = 1
 
    length = len(A)
    no_divided = []
    get_num = {}  # 用字典存储已经得到的非因子数个数，利用空间换时间
    for j in A:
        if j in get_num:
            no_divided.append(get_num[j])
        else:
            count_j_factor = 0
            for factor in range(1, int(j ** 0.5) + 1):
                if j % factor == 0:
                    if factor in element_dict:
                        count_j_factor += element_dict[factor]
                    other_factor = int(j / factor)
                    if other_factor != factor and other_factor in element_dict:
                        count_j_factor += element_dict[other_factor]
            no_divided_count = length - count_j_factor  # 非因子数等于所有的个数减去因子占的总个数
            no_divided.append(no_divided_count)  
            get_num[j] = no_divided_count
    return no_divided

• 结果

image

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

image image