Python:分解质因数

这篇具有很好参考价值的文章主要介绍了Python:分解质因数。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

把一个合数用质因数相乘的形式表示出来,叫做分解质因数. 分解质因数常见方法是短除法,也可以用Python实现.

给出三种分解质因数的代码:文章来源地址https://www.toymoban.com/news/detail-739252.html

Z=int(input('x{x∈Z}='))
print(Z,'= ',end='')

if Z<0:
    Z=abs(Z)
    print('-',end='')

flag=0
if Z<=1:
    print(Z)
    flag=1


while True:
    if flag:
        break
    for i in range(2, int(Z+1)):
        if Z%i==0:
            print("%d"%i, end='')
            if Z==i:
                flag=1
                break
            print('×', end='')
            Z/=i
            break
n = input("合数:")
if n.isdigit():
    n = int(n)
else:
    print("输入非法,请输入一个合数")
    exit()
 
if n < 2:
    print("请输入一个大于2的合数")
    exit()
 
def isZhishu(n):  # 判断是否是质数
    for i in range(2, n):
        if n % i == 0:  # 不是质数
            return False
    else:
        return True
 
l0 = []
def fenjie(n):
    i = 2
    while i < n + 1:
        if n % i == 0:
            l0.append(i)
            n /= i
        else:
            i += 1
 
 
if not isZhishu(n):
    fenjie(n)
    str0 = ''
    for i in l0:
        str0 = str0 + str(i) + "*"
    str0 = str0[:-1]  # 去掉最后一个星号
    print("%s=%s" % (n, str0))
else:
    print("%s是一个质数,请输入一个合数" %n)
#MillerRabin素数判定,结合Pollard_rho递归分解,效率极高
 
import random
from collections import Counter
 
def gcd(a, b):
    if a == 0:
        return b
    if a < 0:
        return gcd(-a, b)
    while b > 0:
        c = a % b
        a, b = b, c
    return a
        
def mod_mul(a, b, n):
    result = 0
    while b > 0:
        if (b & 1) > 0:
            result = (result + a) % n
        a = (a + a) % n
        b = (b >> 1)
    return result
     
def mod_exp(a, b, n):
    result = 1
    while b > 0:
        if (b & 1) > 0:
            result = mod_mul(result, a, n)
        a = mod_mul(a, a, n)
        b = (b >> 1)
    return result
     
def MillerRabinPrimeCheck(n):
    if n in {2, 3, 5, 7, 11}:
        return True
    elif (n == 1 or n % 2 == 0 or n % 3 == 0 or n % 5 == 0 or n % 7 == 0 or n % 11 == 0):
        return False
    k, u = 0, n - 1
    while not (u & 1) > 0:
        k += 1
        u = (u >> 1)
    random.seed(0)
    s = 5
    for i in range(s):
        x = random.randint(2, n - 1)
        if x % n == 0:
            continue
        x = mod_exp(x, u, n)
        pre = x
        for j in range(k):
            x = mod_mul(x, x, n)
            if (x == 1 and pre != 1 and pre != n - 1):
                return False
            pre = x
        if x != 1:
            return False
        return True
         
def Pollard_rho(x, c):
    (i, k) = (1, 2)
    x0 = random.randint(0, x)
    y = x0
    while 1:
        i += 1
        x0 = (mod_mul(x0, x0, x) + c) % x
        d = gcd(y - x0, x)
        if d != 1 and d != x:
            return d
        if y == x0:
            return x
        if i == k:
            y = x0
            k += k
 
def PrimeFactorsListGenerator(n):
    result = []
    if n <= 1:
        return None
    if MillerRabinPrimeCheck(n):
        return [n]
    p = n
    while p >= n:
        p = Pollard_rho(p, random.randint(1, n - 1))
    result.extend(PrimeFactorsListGenerator(p))
    result.extend(PrimeFactorsListGenerator(n // p))
    return result
 
def PrimeFactorsListCleaner(n):
    return Counter(PrimeFactorsListGenerator(n))
                   
PrimeFactorsListCleaner(1254000000)

到了这里,关于Python:分解质因数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 洛谷B2084质因数分解

    已知正整数 n 是两个不同的质数的乘积,试求出较大的那个质数。 输入只有一行,包含一个正整数 n(6n1000000000)。 输出只有一行,包含一个正整数 p,即较大的那个质数。 输入 #1 输出 #1

    2024年02月22日
    浏览(36)
  • 洛谷——P1069 [NOIP2009 普及组] 细胞分裂(分解质因数,唯一分解定理)

    Hanks 博士是 BT(Bio-Tech,生物技术)领域的知名专家。现在,他正在为一个细胞实验做准备工作:培养细胞样本。 Hanks 博士手里现在有 N N N 种细胞,编号从 1 ∼ N 1 sim N 1 ∼ N ,一个第 i i i 种细胞经过 1 1 1 秒钟可以分裂为 S i S_i S i ​ 个同种细胞( S i S_i S i ​ 为正整数)。

    2024年01月16日
    浏览(51)
  • Python中查找质因数

    如何在Python中进行素因式分解。 在数学中,一个数的因数是指那些可以除以给定数并留下零余数的数字。 质数是只有两个因数的独特数字,一个和数字本身。这类数字的一些例子是3,7,11,13,等等。 素数因数化是指找到所有乘以原数的素数。我们可以考虑一个简单的例子:数字

    2024年02月10日
    浏览(46)
  • 试题 C: 质因数个数

    萎了,整个人都萎了 快三天都没刷题了,想着明天就蓝桥杯了,就找了个真题做了下 可以看得出来这题很简单 但是没有测试点给我用,所以我的代码不保证正确性 代码如下:

    2024年04月13日
    浏览(36)
  • 质因数算法(C/C++)

    目录 1  分解质因数 2  打印质数表 2.1  O(n^2)算法(暴力法) 2.2  O(nlogn)算法(埃氏筛) 2.3  O(n)算法(线性筛) 3  计算因数和 说明:这里不需要担心没有筛选质数的问题,因为是从小到大循环,不可能存在分解出合数的情况(例如:2第一个循环,所有2的倍数都已

    2023年04月09日
    浏览(39)
  • 蓝桥杯双周赛算法心得——铺地板(质因数)

    大家好,我是晴天学长,这是第二周的蓝桥杯的双周赛,题可出的又好又灵活啊!真不错!💪💪💪 1) .铺地板 2) .算法思路 1.导入java.util包中的Scanner类,以从用户那里读取输入。 2.main方法是程序的入口点。 3.创建一个Scanner对象,用于从标准输入读取输入。 4.从用户那里读取

    2024年02月08日
    浏览(43)
  • [保研/考研机试] KY7 质因数的个数 清华大学复试上机题 C++实现

    求正整数N(N1)的质因数的个数。 相同的质因数需要重复计算。如120=2*2*2*3*5,共有5个质因数。 输入描述: 可能有多组测试数据,每组测试数据的输入是一个正整数N,(1N10^9)。 输出描述: 对于每组数据,输出N的质因数的个数。 输入: 输出: 只需要判断因数是否能够整除当前

    2024年02月13日
    浏览(47)
  • Python使用递归法对整数进行因数分解

    所谓因数分解,是指把一个整数变成其所有质因数相乘的形式,例如10=2*5, 39000=2*2*2*3*5*5*5*13。 from random import randint def factors(num, fac=[]):     #每次都从2开始查找因数     for i in range(2, int(num**0.5)+1):         #找到一个因数         if num%i == 0:             fac.append(i)        

    2023年04月23日
    浏览(38)
  • C. Multiplicity(DP + 分解因数)

    Problem - C - Codeforces 给定一个整数数组a1,a2,...,an。 如果可以从a中删除一些元素得到b,则称数组b为a的子序列。 当且仅当对于每个i(1≤i≤k),bi是i的倍数时,数组b1,b2,...,bk被称为好。 在模109+7下找到a中好的子序列的数量。 如果两个子序列的包含数字的索引集合不同

    2024年02月02日
    浏览(32)
  • 数据分析课程设计(数学建模+数据分析+数据可视化)——利用Python开发语言实现以及常见数据分析库的使用

    目录 数据分析报告——基于贫困生餐厅消费信息的分类与预测 一、数据分析背景以及目标 二、分析方法与过程 数据探索性与预处理 合并文件并检查缺失值 2.计算文件的当中的值 消费指数的描述性分析 首先对数据进行标准化处理 聚类模型的评价 聚类模型的结果关联 利用决

    2024年02月12日
    浏览(56)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包