prime - Code666 (代码贴、代码片段) prime - Code666 (代码贴、代码片段) http://www.code666.cn/ en Re: prime | 我看懂了！！！ http://www.code666.cn/view/05c05fcc Sun, 15 Jan 2023 16:36:16 +0800 4n0n4me http://www.code666.cn/view/05c05fcc
  1. import math
  2. 分解结果 = dict()
  3. 已知素数 = [2, 3]
  4. 当前素数序号 = 0
  5.  
  6.  
  7. def getPrime(待分解数: int) -> str:
  8.     global 分解结果, 已知素数, 当前素数序号
  9.     assert isinstance(待分解数, int)
  10.     assert 待分解数 > 1
  11.  
  12.     def 判断素数(_判断所用因数们: list, _待判断数: int):
  13.         _待判断数平方根 = math.floor(math.sqrt(_待判断数))
  14.         for _当前因数 in _判断所用因数们:
  15.             if _待判断数 % _当前因数 == 0:
  16.                 return False  # 不是素数
  17.             elif _当前因数 > _待判断数平方根:
  18.                 return True  # 是素数
  19.  
  20.     def 更新素数表():
  21.         _下一个素数 = 已知素数[-1]+2
  22.         while not 判断素数(已知素数, _下一个素数):
  23.             _下一个素数 += 2
  24.         已知素数.append(_下一个素数)
  25.         return
  26.  
  27.     def 递归处理(待分解因数: int) -> None:  # **这一次**待分解的数字
  28.         global 当前素数序号
  29.         待分解因数平方根 = math.floor(math.sqrt(待分解因数))  # 待分解的数字的平方根
  30.         当前素数 = 已知素数[当前素数序号]  # 取一个素数
  31.  
  32.         print(f'{待分解因数}分解开始')
  33.         print(f'当前素数：{当前素数}')
  34.  
  35.         if 待分解因数 == 1:  # 乘以一不用写了，乘不乘没区别
  36.             print(f'当前无需分解，分解结果：{分解结果}')
  37.             return
  38.  
  39.         # (*)
  40.         if 待分解因数 == 当前素数:  # 待分解的数就是这次的素数，直接算进去
  41.             print(f'{待分解因数}就是当前素数，加入分解结果')
  42.             if 待分解因数 in 分解结果:
  43.                 分解结果[待分解因数] += 1
  44.             else:
  45.                 分解结果.update({待分解因数: 1})
  46.  
  47.             return
  48.  
  49.         if not 待分解因数 % 当前素数:
  50.             print(f'可以直接用{当前素数}分解{待分解因数}进行递归')
  51.         else:
  52.             print(f'更新素数以后才能找到分解{待分解因数}的方法或者确定它是素数')
  53.  
  54.         while 待分解因数 % 当前素数:  # 待分解的数字不能被当前素数整除
  55.  
  56.             # 如果某因数在待分解数中的指数大于一
  57.             # 当待分解数从最小的素数开始分解
  58.             # 会先除到剩下某因数的N次方的倍数
  59.             # 当某因数以下的素数都被分解出去了
  60.             # 某因数成为最小的素数
  61.             # 因此当前素数会一直走到某因数
  62.             # 此时不满足循坏条件，直接退出循环，进行递归处理。
  63.             # 然后这个递归处理会分别处理某因数，和某因数的N-1次方的倍数
  64.             # 而此时当前素数已经走到某因数了！
  65.             # 因此，指数大于一的因数不会再(#)被加入！！！
  66.  
  67.             if 当前素数 > 待分解因数平方根:  # (#)
  68.                 print(f'当前素数大于待分解因数平方根，{待分解因数}直接加入分解结果')
  69.                 # 待分解因数不能被此前的任何素数整除
  70.                 # 甚至此时当前素数也没有走到待分解因数
  71.                 # 因此待分解因数此前没有被从(*)加入
  72.  
  73.                 # 而当前素数没有走到待分解因数，就说明递归处理中没有处理过“待分解因数的平方的倍数”
  74.                 # 就说明待分解因数在待分解数中的指数为一
  75.  
  76.                 分解结果.update({待分解因数: 1})
  77.                 return
  78.             else:
  79.                 # 取一个新的素数
  80.                 当前素数序号 += 1
  81.                 if 当前素数序号 == len(已知素数):
  82.                     更新素数表()
  83.                 当前素数 = 已知素数[当前素数序号]
  84.                 print(f'更新当前素数：{当前素数}')
  85.  
  86.         递归处理(当前素数)  # 递归处理的就是当前素数，所以直接在(*)加入，后面的操作都不会进行
  87.         递归处理(待分解因数//当前素数)  # 接着分，最后就是把最后一个（最大的一个）素因数分解出去以后这边就是1，然后这个函数就该一层层return出去了
  88.  
  89.         print(f'{待分解因数}分解完毕')
  90.  
  91.     递归处理(待分解数)
  92.  
  93.     res = f'{待分解数}={"*".join([f"{k}^{v}^" for k, v in 分解结果.items()])}'
  94.     res = res.replace('*', '\\*').replace('^1^', '')
  95.     分解结果.clear()
  96.     当前素数序号 = 0
  97.     return res
  98.  
  99.  
  100. print(getPrime(36))
  101.  
]]> Re: prime | pwp... http://www.code666.cn/view/74de8db0 Sun, 15 Jan 2023 12:01:18 +0800 4n0n4me http://www.code666.cn/view/74de8db0
  1. import math, random
  2. tmp_result = dict()
  3. prime_numbers = [2,3]
  4. prime_index = 0
  5. def getPrime(i: int) -> str:
  6.     global tmp_result,prime_numbers,prime_index
  7.     if i == 0:
  8.         tmp = list(map(str,random.choices(prime_numbers,k=random.randrange(3,13))))+['0']
  9.         random.shuffle(tmp)
  10.         tmp = f"0={'*'.join(tmp)}"
  11.         tmp = tmp.replace('*','\\*')
  12.         return tmp
  13.     elif i == 1:
  14.         return "没法分解啊啊啊啊(+﹏+)"
  15.     def _judgePrime(kr: list, ss: int):
  16.         ll = math.floor(math.sqrt(ss))
  17.         for oo in kr:
  18.             if ss % oo == 0:
  19.                 return True
  20.             elif oo > ll:
  21.                 return False
  22.     def _updatePrime():
  23.         dx = prime_numbers[-1]+2
  24.         while _judgePrime(prime_numbers,dx):
  25.             dx += 2
  26.         prime_numbers.append(dx)
  27.         return
  28.     def _handle(ii: int) -> None:
  29.         global prime_index
  30.         kk = math.floor(math.sqrt(ii))
  31.         ww = prime_numbers[prime_index]
  32.         if ii == 1:
  33.             return
  34.         if ii == ww:
  35.             if ii in tmp_result:
  36.                 tmp_result[ii] += 1
  37.             else:
  38.                 tmp_result.update({ii:1})
  39.             return
  40.         while ii%ww:
  41.             if ww > kk:
  42.                 if ii in tmp_result: # 为什么不需要这样
  43.                     tmp_result[ii] += 1
  44.                 else:
  45.                     tmp_result.update({ii:1})
  46.                 return
  47.             else:
  48.                 prime_index += 1
  49.                 if prime_index == len(prime_numbers):
  50.                     _updatePrime()
  51.                 ww = prime_numbers[prime_index]
  52.         _handle(ww)
  53.         _handle(ii//ww)
  54.     _handle(i)
  55.     res = f'{i}={"*".join([f"{k}^{v}^" for k, v in tmp_result.items()])}'
  56.     res = res.replace('*','\\*').replace('^1^','')
  57.     tmp_result.clear()
  58.     prime_index = 0
  59.     return res
]]>