HJ质数因子
有勇气的牛排
972
算法
2022-06-26 18:20:29
描述
功能:输入一个正整数，按照从小到大的顺序输出它的所有质因子（重复的也要列举）（如180的质因子为2 2 3 3 5 ）
数据范围：1≤n≤2×109+14
输入描述：
输入一个整数
输出描述：
按照从小到大的顺序输出它的所有质数的因子，以空格隔开。
示例1
输入：180
输出：2 2 3 3 5
质数因子解释：
百度百科：https://baike.baidu.com/item/质因子
概念：
解法：
- 质数范围一定在 根号下n
- n除以所有质因子，结果为1：24/2/2/2/3=1
牛客HJ Python
import math
n = int(input())
for i in range(2, int(math.sqrt(n) + 1)):
while n % i == 0:
print(i, end=" ")
n = n // i
if n > 2:
print(n)
<p><strong>描述</strong><br />
功能:输入一个正整数，按照从小到大的顺序输出它的所有质因子（重复的也要列举）（如180的质因子为2 2 3 3 5 ）</p>
<p>数据范围：1≤n≤2×10<sup>9</sup>+14</p>
<p><strong>输入描述：</strong><br />
输入一个整数</p>
<p><strong>输出描述：</strong><br />
按照从小到大的顺序输出它的所有质数的因子，以空格隔开。</p>
<p><strong>示例1</strong></p>
<pre><div class="hljs"><code class="lang-shell">输入：180
输出：2 2 3 3 5
</code></div></pre>
<p><mark>质数因子解释：</mark></p>
<p>百度百科：<a href="https://baike.baidu.com/item/%E8%B4%A8%E5%9B%A0%E5%AD%90" target="_blank">https://baike.baidu.com/item/质因子</a><br />
<img src="https://static.couragesteak.com/article/05228f7807367420d077f25d7848baf7.png" alt="image.png" /></p>
<p>概念：</p>
<ul>
<li>一个数可以被它所有的质因子表示</li>
</ul>
<p>解法：</p>
<ul>
<li>质数范围一定在 根号下n</li>
<li>n除以所有质因子，结果为1：24/2/2/2/3=1</li>
</ul>
<p>牛客HJ Python</p>
<pre><div class="hljs"><code class="lang-python"><span class="hljs-keyword">import</span> math
n = <span class="hljs-built_in">int</span>(<span class="hljs-built_in">input</span>())
<span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> <span class="hljs-built_in">range</span>(<span class="hljs-number">2</span>, <span class="hljs-built_in">int</span>(math.sqrt(n) + <span class="hljs-number">1</span>)):
<span class="hljs-keyword">while</span> n % i == <span class="hljs-number">0</span>:
<span class="hljs-built_in">print</span>(i, end=<span class="hljs-string">" "</span>)
n = n // i
<span class="hljs-comment"># 打印剩下的质数</span>
<span class="hljs-keyword">if</span> n > <span class="hljs-number">2</span>:
<span class="hljs-built_in">print</span>(n)
</code></div></pre>
留言