精华内容
下载资源
问答
  • 质因子分解 Python

    2021-04-19 18:12:23
    使用Python实现质因子分解(分解质因子)。包含判断质数,质因子分解

    质因子分解 PythonPython

    要做质因子分解,首先需要明白什么是质数,以及如何快速判断质数。

    质数

    质数,也称素数,是只能被1和其本身整除的数,规定1不是质数。

    质数的判断可以详见我另一篇博客 判断质数 Python Java C++

    def isPrime(n: int) -> bool:
        if n <= 3:
            return n >= 2
        if (n + 1) % 6 != 0 and (n - 1) % 6 != 0:
            return False
        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:
                return False
        return True
    

    质因子分解

    质因子分解,故名思意,将一个数分解成所有因子都是质数。

    首先判断待分解这个数本身是不是质数,如果他本身就是一个质数的话,那他的质因子就是他自己,因为1不是质数。

    如果不是质数,就从2开始,往上一个个质数除。如果可以整除这个质数,那么这个质数就是其一个因子。保存这个质数到一个列表中,再将待分解的数整除这个质数,继续分解即可。

    质数列表,可以用列表生成式[i for i in range(2, 10) if isPrime(i)]生成一个质数列表,这个刚开始生成几个就够了,如果数量不够的话,再补充。如果刚开始数量就大的话,复杂度会比较大,大部分数不需要这么大,真用到了,后边再补充就行

    if i >= len(primes) - 1:
    	primes += [i for i in range(i + 1, i + 1000) if isPrime(i)]
    

    完整代码

    # 判断是否是质数
    def isPrime(n: int) -> bool:
        if n <= 3:
            return n >= 2
        if (n + 1) % 6 != 0 and (n - 1) % 6 != 0:
            return False
        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:
                return False
        return True
    
    
    # 质因子分解
    def factor(n: int) -> list[int]:
        ans = []
        if isPrime(n):  # 判断本身是否是质数
            ans.append(n)
            return ans
        primes = [i for i in range(2, 10) if isPrime(i)]  # 生成待循环整除的质数列表
        i = 0  # 初始化下标
        while not isPrime(n):
            if n % primes[i] == 0:  # 判断待分解的数是否可以整除这个质数,若能,则这个质数是其一个因子
                ans.append(primes[i])  # 保存质因子到列表中
                n //= primes[i]  # 待分解数整除该质数
                i = 0  # 重置质数列表下标(重新从2,3,5...开始判断整除)
            else:
                i += 1  # 如果不能整除,则下标后移,判断下一个质数是否能整除
                if i >= len(primes) - 1:  # 如果质数列表的长度不够,就扩充一部分,如果遇到数组超限,就加大1000这个判断区间值
                    primes += [i for i in range(i + 1, i + 1000) if isPrime(i)]
        ans.append(n)  # 保存n,由于while循环判断,此时n是最后一个质数
        return ans
    
    
    print(factor(2021041820210418)) #输入待分解的数,即可输出质因子列表
    
    展开全文
  • python 1071:分解质因子

    2020-12-13 10:57:40
    a=eval(input()) for i in range(2,a): while a%i==0: print(i,end=" ") a=a//i
    a=eval(input())
    for i in range(2,a):
        while a%i==0:
            print(i,end=" ")
            a=a//i
    
    展开全文
  • python3 分解质因子

    千次阅读 2018-07-11 15:22:18
    def isPrime(num): if num ==1: return False else: for i in range(2,num): if(num%i==0): return False return True num = int(input('请输入:')) li...
    def isPrime(num):
        if num ==1:
            return False
        else:
            for i in range(2,num):
                if(num%i==0):
                    return False
            return True
    
    
    num = int(input('请输入:'))
    list = []
    
    while isPrime(num) == False:
        for j in range(2,num):
            if isPrime(j) and num%j ==0 :#关键逻辑:能整出质数
                num = num//j
                list.append(j)
                break
    list.append(num)
    print(list)

    展开全文
  • 1071: 分解质因子 题目描述 将一个正整数分解质因数,例如,输入90,输出2 3 3 5。 输入 输入一个正整数n(2<=n<=2000)。 输出 从小到大输出n的所有质因子,每两个数之间空一格。 样例输入 20 样例输出 2 2 5...

    1071: 分解质因子

    题目描述

    将一个正整数分解质因数,例如,输入90,输出2 3 3 5。

    输入

    输入一个正整数n(2<=n<=2000)。

    输出

    从小到大输出n的所有质因子,每两个数之间空一格。

    样例输入

    20

    样例输出

    2 2 5

    n=eval(input())
    for i in range(2,n):
        while n%i==0:
            print("%d"%i,end="")
            n=n//i
            if(n==1):
                print("",sep="",end="")
            else:
                print(" ",end="")
    展开全文
  • 1071: 分解质因子 时间限制: 1 Sec 内存限制: 128 MB 提交: 17401 解决: 11301 [状态] [讨论版] [提交] [命题人:admin] 题目描述 将一个正整数分解质因数,例如,输入90,输出2 3 3 5。 输入 输入一个正整数n(2<...
  • 区别:获取因子后,分解质因数需要判断因子是不是质数,如果是,则该因子因数,如果不是,则继续分解,直到所有的因子的都是质数为止 一、分解质因数 分解质因数:把一个合数写成几个质数相乘的形式表示,比如36...
  • Python - 分解因子

    2019-09-09 13:29:03
    1. 素数判断 ----- 分解因子 ----- 分解质因子 2. 最大公因数(gcd) 3. 最大公因字符串 ----- 最小公因字符串 素数: #data def func1(data): if not[x for x in range(2,int(data**0.5+1)) if not data%x] ...
  • python程序分解质因数

    2018-05-01 22:09:55
    质因数(素因数或质因子)在数论里是指能整除给定正整数的质数,这里通过运行python程序分解质因数
  • ZZULIOJ-1071,分解质因子Python

    千次阅读 2020-04-09 19:08:19
    题目描述: 将一个正整数分解质因数,例如,输入90,...从小到大输出n的所有质因子,每两个数之间空一格。 样例输入: 20 样例输出: 2 2 5 程序代码: n=int(input()) for i in range(2,n//2+1) ...
  • #从控制台输入一个数,分解质因数num=int(input("输入一个数"))i=2while num!=1 : if num%i==0: print(i) num=num//i else: i+=1 #从控住天输入一个字符串,返回这个字符串中有多少个单词1str=input()#输入一个字符...
  • 2019独角兽企业重金招聘Python工程师标准>>> ...
  • Python解决合数分解问题

    千次阅读 2020-04-14 17:07:19
    编写程序,用户输入一个合数,将其分解因式输出,如:60=223*5,每个因子都是质数,质数判断过程在一个自定义函数内完成。 代码: def isprime(n): import math if n <= 1: return False r = int(math.sqrt(n))...
  • 质因数(素因数或质因子):在数论里是指能整除给定正整数的质数。除了1以外,两个没有其他共同质因子的正整数称为互质。因为1没有质因子,1与任何正整数(包括1本身)都是互质 简而言之就是:质因数就是一个数的...
  • python练习1 质数分解

    千次阅读 2014-08-14 11:46:12
    9、实战练习 ...学了这么多东西,是不是跃跃欲试了,下面让我们来做一道数学题检验一下成果。...写一个函数接受一个int型参数,判断...利用上面两个函数编写一个函数,接受一个int型参数,返回这个参数的最大质因子
  • Python3 初学实践案例(11)判断质数以及计算一个数字的质因数昨天晚上看到群里有人问如何计算质因数,我想了一下,实现了这个...正整数的因数分解可将正整数表示为一连串的质因子相乘,质因子如重复可以用指数表示。根
  • 问题:编写一个可以将任意正整数...思路:给出整数N,设定d从N-1开始递减,假如N%d等于0,则此时(N/d)是N的一个质因子,同时使N=d,不断迭代,直至d=1。l=[]def depart(n): d = n-1; while d > 1: if n % d == 0 :
  • Python编程之找完数

    千次阅读 2019-03-23 08:48:43
    问题描述:一个数如果恰好等于它的因子之和,这个数就称为"完数"。例如6=1+2+3.编程找出1000以内的所有完数。 程序分析:对n进行分解质因数,应先找到一个最小的质数k,然后按下述步骤完成: (1)如果这个质数恰...
  • Python3程序设计实验一

    千次阅读 2018-02-02 23:39:53
    质因子 1.程序设计说明 编写函数,接受一个整数,返回该数所有的质因子。 2.程序设计思路 通过input函数读入一个字符串,用异常处理来判断其是否为合法的输入:若否,则抛出异常,否则继续执行。用分解质...
  • 题目:原题链接(简单) 题目标签: 解法 时间复杂度 空间复杂度 执行用时 ...Ans 1 (Python) ...Ans 2 (Python) ...Ans 3 (Python) ...LeetCode的Python执行...解法一(分解质因子,再由质因子组合因子): def checkPerfec
  • python练手小程序之二

    2018-10-29 20:37:48
    程序分析:对输入的数j进行因子分解(这里的因子不是因数): (1)初始化一个s变量,将j赋值给s,使用循环和取余来判断1-j中的i是否能被j整除,如是则使用增量赋值s-=I ,即s = s-i。 (2)最后判断s是否等于0,6-1-2...
  • python3 题解(5)

    2019-09-02 11:10:21
    分解质因数 【问题】给定一个正整数,例如:90,求它的因数乘积形式。 90 = 2 * 3 * 3 * 5 特别地,如果给定的是一个素数,则分解就是它自身。 17 = 17 这个问题很基础,也很重要。 首先,从题面的意思看,是要...
  • Python案例集锦-0414.docx

    2018-11-27 23:23:22
    程序34:分解质因子 29 程序35:取整数右端的4~7位 30 程序36:判断4位回文数 31 程序37:汉诺塔(递归函数) 32 程序38:判断闰年 33 程序39:寻找自幂数(38) 34 程序40:多维数据 35 程序41: 验证哥德巴赫猜想 ...
  • 题目:一个数如果恰好等于它的因子之和,这个数就称为"完数"。例如6=1+2+3.编程找出1000以内的所有完数 思路: n进行分解质因数,应先找到一个最小的质数k,然后按下述步骤完成: (1)如果这个质数恰等于n,则说明...
  • Python【每日一问】27

    2019-05-23 12:38:00
    【基础题1】:将一个正整数分解质因数。例如:输入 90, 打印出 90=2*3*3*5 。 【基础题2】:一个数如果恰好等于它的因子之和,这个数就称为“完数” 。例如6=1+2+3。请找出 1000 以内的所有完数。 【提高题】:...

空空如也

空空如也

1 2
收藏数 35
精华内容 14
关键字:

python质因子分解

python 订阅