Python 计算当真因子个数为偶数个时为幸运数,计…

2019-04-20 08:53:08来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

晚饭后朋友发来个问题,正好无事做,动手写了一下

若一个正整数有偶数个不同的真因子,则称该数为幸运数。如4含有2个真因子为 1 和 2 。故4是幸运数。求【2,100】之间的全部幸运数之和。

常规思路

被除数一直除以 1 2 3 ... 直到除以它自身,不过这种比较消耗资源(周知python简洁但效率不高)

getf.py

def get_Factor(x):
    """
    n    需要求真因数的数(被除数)  x
    x    除数  y
    rem    余数
    quo    商
    """
    if x == 0: return [0]
    if x == 1: return [1]
    f_list = []
    for y in range(1,x):#定义y是除数
        rem = x % y
        quo = x // y
        if rem == 0:# 如果x可以被y整除
            if y not in f_list:
                f_list.append(y)
                if quo not in f_list:
                    f_list.append(quo)
                    continue
                continue
            continue
        
    f_list.sort(reverse = False)
    f_list.pop()
    #是一个一个加进去,排个序后删除本身
    return x , f_list


def get_Luckynum(a, b):
    Luckynum = []
    for i in range(a,b+1):
        i,f_list = get_Factor(i)
        if len(f_list) % 2 == 0:
            Luckynum.append(i)
#           print(i,"的真因数:",f_list,"个数为",len(f_list),"个,■■是■■")
#        else:
#            print(i,"的真因数为:",f_list,"个数为",len(f_list),"个,♦♦不是♦♦")
            
            
    return Luckynum, sum(Luckynum)

main.py

# -*- coding: utf-8 -*-
"""
Created on Fri Apr 19 19:32:33 2019

@author: Administrator
"""
import getf

a = int(input("请输入最小值:"))
b = int(input("请输入最大值:"))
Luckynum, sum_Luckynum = getf.get_Luckynum(a,b)
print('区间 [{0},{1}] 的幸运数包含:{2}'.format(a, b, Luckynum))
print('它们的总和是:{0}'.format(sum_Luckynum))

另一个思路:被除数区间的定义

稍微思考一下

a*b = c   a变大b就会变小   a变小b就会变大 

假设a永远是最小 b永远是最大的哪个

那么 a 和 b 的它们最大值,肯定是 √c

该思路就是让 c 求商的时候,不用像常规思路一般一直除到本身(如65,要除以1..2..3..4......65 )资源消耗大,效率低下

而是一直除到 √c  (如65,要除以1..2..3..4...一直到√65  就停止遍历)

当然 遍历到 √c 的时候 a = b 这个就在加个判断就好了,不允许重复

如下

import math

def new_get_Factor(x):
    if x == 0: return [0]
    if x == 1: return [1]
    f_list = []
    for y in range(1,int(math.sqrt(x)) + 1):
        #(1,根号x+1)确保能够遍历到根号x
        rem = x % y
        quo = x // y
        if rem == 0:
            f_list.append(y)
            if y != quo:
                f_list.append(quo)
                continue
            continue
        
    f_list.sort(reverse = False)
    f_list.pop()
    return x,f_list

 


原文链接:https://www.cnblogs.com/Alins/p/10740182.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:day10-python基础之字符串

下一篇:预测python数据分析师的工资