首页 > 试题广场 >

质数因子

[编程题]质数因子
  • 热度指数：1205995 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
\hspace{15pt}对于给定的整数 n，从小到大依次输出它的全部质因子。即找到这样的质数 p_1, p_2, \cdots, p_k，使得 n = p_1 \times p_2 \times \cdots \times p_k。

输入描述:
\hspace{15pt}在一行上输入一个整数 n \left( 2 \leqq n \leqq 2 \times 10^9 + 14 \right) 代表待分解的整数。


输出描述:
\hspace{15pt}在一行上从小到大输出若干个整数，代表 n 的质因子。
示例1

输入

180

输出

2 2 3 3 5

说明

\hspace{15pt}在这个样例中，180 = 2 \times 2 \times 3 \times 3 \times 5。
示例2

输入

47

输出

47
算法知识视频讲解
添加回答
Python3
东凡头像 东凡
n = int(input())
nums = []
k = int(n ** (0.5)) + 1
for i in range(2, k + 1):
    while n % i == 0:
        nums.append(str(i))
        n = n // i
if n > 2:
    nums.append(str(n))
if len(nums) ==1:
    print(nums[0])
else:
    print(' '.join(nums))

发表于 2025-04-09 21:48:05 回复(0)
Python3
海洋游人头像 海洋游人
n = int(input())

prime_factor_list = []

"""
Important Notes:
1. We iterate from 2 to (square root of n)+1 because we do not
need to iterate beyond this number. The reason is that any
factor beyond this number would be multiple of the prime
numbers covered previously.
2. We use the for-while loop structure to handle the case where
we need to repeatedly append the same factor to the list.
"""

for i in range(2, int(n**0.5)+1):
    while n%i == 0:
        prime_factor_list.append(i)
        n = n//i

if n > 2:
    prime_factor_list.append(n)

print(" ".join(map(str, prime_factor_list)))
发表于 2025-04-09 03:16:18 回复(0)
Python3
希望早日成为社会栋梁头像 希望早日成为社会栋梁

用lst存储待输出的因子，设计求因子的函数divisor以及判断质数的函数isPrime
while循环判断lst内是否都是质数,全是质数就可以控制lst列表在一行内输出了：

import math

def isPrime(n): #判断是否为素数的函数 素数返回True 合数返回False
    n_root = int(math.sqrt(n))
    if n == 2 or n == 3:
        return True
    else:
        for i in range(2, n_root + 1):
            if n % i == 0:
                return False
    return True

def divisor(p): # 求数的因子的函数，返回两个和最小的因子 list
    p_root = int(math.sqrt(p))
    j = [1, p]
    for i in range(p_root, 0, -1):
        if p % i != 0:
            pass
        else:
            j[0] = i
            break
    j[1] = int(p/(j[0]))
    if j[0] == 1:
        l = list()
        l.append(j[1])
        return l
    else:
        return j

def bool_lst(lst):
    len_f = len(lst)
    i = 0
    for item in lst:
        if item:
            i += 1
    if i == len_f:
        return True
    else:
        return False

s = int(input()) # 接收输入的整数 int

lst = [s] # 存储待输出的质因子

len_lst = len(lst) # 待输出列表的长度 int

lst_flag = list() # 判断待输出列表是否全为质数的指标 全是质数则为True 默认不是质数 lst

for i in range(0, len_lst):
    lst_flag.append(isPrime(lst[i])) # 更新

lst_bool = bool_lst(lst_flag) # 更新 bool 

while (lst_bool == False): # 待输出因子列表中有合数
    for item in lst:
        s_new = divisor(item) # s_new是有两个因子的列表
        lst = lst + s_new # 在末尾加入两个因子
        lst.remove(item) # 删除被拆解的数
    len_lst = len(lst) # 更新len_lst
    lst_flag = list()
    for i in range(0, len_lst):
        lst_flag.append(isPrime(lst[i])) # 更新lst_flag
    lst_bool = bool_lst(lst_flag)

for item in lst:
    if item == 1:
        lst.remove(item)
lst.sort()

if lst_bool:
    print(" ".join(str(i) for i in lst)) # 控制列表在一行内输出
发表于 2025-03-23 23:32:46 回复(0)
Python3
牛客245835099号头像 牛客245835099号
不考虑质数都是耍流氓，但是！可以偷鸡，i每次加2即可剩下一半时间（需要单独处理2，从3开始循环），同时对大数求平方根来减少循环次数，如果i>sqrt_n则n一定不可分解。

import math
if __name__=="__main__":
    n = int(input())
    i = 2
    result = []
    while n % 2 == 0:
        result.append(2)
        n = n//2
    i = 3
    sqrt_n = math.sqrt(n)
    while i <=sqrt_n:
        while n%i==0:
            result.append(i)
            n = n//i
        i += 2
    if n>1:
        result.append(n)

    for index, num in enumerate(result):
        print(num, end=' ')


发表于 2025-02-24 17:58:22 回复(0)
Python3
牛客861341727号头像 牛客861341727号
在分解质因数的算法中，使用for i in range(2, int(n ** 0.5) + 1)来遍历可能的质因数，将遍历上限设置为int(n ** 0.5) + 1主要基于以下数学原理和算法优化考虑：

数学原理


对于任意一个正整数n，如果它不是质数，那么它一定可以分解为两个因数a和b，即n = a * b，其中a ≤ b。

由此可得
，也就是 。这意味着，在分解质因数时，如果n存在小于等于 的因数，我们就能通过遍历到 找到它；反之，如果遍历到
都没有找到n的因数，那么n本身就是质数。

代码实现中的细节


  • n ** 0.5：在 Python 中，n ** 0.5用于计算n的平方根。例如，当n = 16时，n ** 0.5的结果是4.0。
  • int(n ** 0.5)：由于range()函数只能接受整数参数，所以需要使用int()函数将n ** 0.5的结果转换为整数。这里的取整是向下取整，比如int(4.9)的结果是4。
  • int(n ** 0.5) + 1：range()函数的结束值是开区间，即不包含结束值本身。所以为了确保能遍历到
这个数（当 为整数时），需要在int(n ** 0.5)的基础上加 1。例如，当n = 16时，int(n ** 0.5)是4，加上 1 后为5，这样range(2, 5)就能遍历到2、3、4，可以完整地检查到所有可能小于等于
  • 的因数。

总结


将遍历上限设置为int(n ** 0.5) + 1是为了在保证能找到所有小于等于
的质因数的前提下，减少不必要的遍历次数，从而提高算法的效率。因为一旦遍历到 都没有找到n的因数，就可以确定n是质数，无需再继续遍历大于 的数。 
import sys

n = int(input())

for i in range(2, int(n ** 0.5) + 1):  # 遍历所有可能的因数，直到 sqrt(n)
    while n % i == 0:  # 如果 i 是 n 的因子
        print(i, end=" ")  # 输出 i
        n = int(n / i)  # 更新 n 为商
if n > 2:  # 如果 n 本身是一个大于 2 的质数
    print(n)  # 输出 n


发表于 2025-02-20 20:33:01 回复(0)
Python3
牛客127723680号头像 牛客127723680号
n = int(input())
b = [] #空字典存放质因子
#2提出来
i = 2
while n%2 == 0:
    n = n//2
    b.append(2)
#接着从3开始，依次加2
i = 3
while i*i <= n: #让n*n囊括所有质因数
    while n%i == 0:
        b.append(i)
        n = n//i
    i += 2
if n>1:
    b.append(n)
print(*b)
发表于 2025-02-14 19:17:24 回复(0)
Python3
死气沉沉的祖国花朵很贪睡头像 死气沉沉的祖国花朵很贪睡
不知道有没有注意到分解出的因数是从小往大排的呢？
n = n1 = int(input())
prime = 2
while prime < n ** 0.5 + 1:
    if n % prime == 0:
        n /= prime
        print(prime, end=" ")
    else:
        prime += 1
if n1 == 1 or n != 1:
    print(int(n))
发表于 2025-02-14 14:47:34 回复(0)
Python3
小琴傷头像 小琴傷
总之小琴优化过了，应该是优秀的代码
发表于 2025-01-14 15:20:46 回复(0)
Python3
牛客307634930号头像 牛客307634930号
s = int(input())
i = 2
m = s**0.5+1
while i <= m:
    if s % i == 0:
        print(i,end=' ')
        s = s/i
    else:
        i += 1
if s != 1:
    print(int(s))
发表于 2024-12-23 10:59:59 回复(0)
Python3
萨拉米给有头像 萨拉米给有 
import sys

n = int(input())

for i in range(2, int(n ** 0.5) + 1):  # 遍历所有可能的因数，直到 sqrt(n)
    while n % i == 0:  # 如果 i 是 n 的因子
        print(i, end=" ")  # 输出 i
        n = int(n / i)  # 更新 n 为商
if n > 2:  # 如果 n 本身是一个大于 2 的质数
    print(n)  # 输出 n

发表于 2024-12-13 14:51:20 回复(0)
Python3
牛客868962590号头像 牛客868962590号
a=int(input())

if a<2000000014:
    while a%2==0:
        print(2,end=' ')
        a=a/2
    for i in range(3,int(a),2):
        while a%i==0:
            print(i,end=' ')
            a=a/i
    if a>2:
        print(int(a),end=' ')
if a==2000000014:
    print(str(2)+' '+str(1000000007))

这个题有问题啊，最后的那个测试用例已经超过最大值了，为啥还能测进去，也可能是我代码太复杂了，刚学只能用笨方法通过最后一个用例了
发表于 2024-12-07 12:24:14 回复(1)
Python3
牛客722483943号头像 牛客722483943号 
import math
def caculate_num(k):
    num=k
    str1=''
    while num%2==0:#循环计算满足2的结果个数，若不满足，则退出while循环，进入下一个代码
        str1+='2'+' '
        num//=2

    for i in range(3,int(math.sqrt(num))+1,2):#质数一定小于根号下num,并且大于2的部分质数一定是奇数，故而步长设置为2
        while num%i==0:#循环判断满足i的情况
            str1+=str(i)+' '
            num//=i

    if num>2:
        str1+=str(num)

    return str1
#计算全部的质数因子
#最优时间复杂度O(sqrt(n))
i_data=int(input())

print(caculate_num(i_data))


发表于 2024-11-15 22:20:22 回复(0)
Python3
Cyber2077头像 Cyber2077 
def prime_factors(n):
    factors = []
    # 处理2这个特殊的质因子
    while n % 2 == 0:
        factors.append(2)
        n //= 2
    # 处理奇数质因子
    for i in range(3, int(n ** 0.5) + 1, 2):
        while n % i == 0:
            factors.append(i)
            n //= i
    # 如果n仍然大于2，则n本身是一个质因子
    if n > 2:
        factors.append(n)
    return factors


prime_list = prime_factors(int(input()))
prime_list = map(str, prime_list)
print(' '.join(prime_list))

发表于 2024-10-31 16:03:01 回复(0)
Python3
牛客132287709号头像 牛客132287709号
a = int(input())
b = []
while a % 2 ==0:
    a = a/2
    b.append("2")
for i in range(3, int(a**0.5)+1,2):
    while a % i == 0:
        a = a/i
        b.append(i)
if a > 2 :
    b.append(int(a))
print(*b)
发表于 2024-10-19 17:14:58 回复(0)
Python3
说什么AI头像 说什么AI 
def isPrime(n):
    flag = 0
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            flag+=1
    if flag:
        return False
    else:
        return True

n = int(input())
for i in range(2,n+1):
    if n>1 and isPrime(n):
        print(int(n))
        break
    else:
        while isPrime(i) and n%i==0:
            n = n/i
            print(i,end=' ')

发表于 2024-10-10 17:08:31 回复(0)
Python3
好想去华为上班呀头像 好想去华为上班呀
def fun1(n):
    # 创建一个空列表，用于存放质因数
    list_Z = []
   
    # 检查 n 是否是偶数（能否被 2 整除）
    while n % 2 == 0:
        # 如果是偶数，将 2 加入质因数列表
        list_Z.append(2)
        # 将 n 除以 2，继续检查是否还有其他 2 的因数
        n //= 2
   
    # 从 3 开始检查奇数因数，直到 n 的平方根
    for i in range(3, int(n**0.5) + 1, 2):
        # 检查 n 是否能被 i 整除
        while n % i == 0:
            # 如果能整除，将 i 加入质因数列表
            list_Z.append(i)
            # 将 n 除以 i，继续检查是否还有其他 i 的因数
            n //= i
   
    # 如果 n 大于 2，说明 n 本身是一个质数因数
    if n > 2:
        # 将 n 加入质因数列表
        list_Z.append(n)
   
    # 返回质因数列表
    return list_Z

# 程序入口，只有在直接运行此脚本时才会执行以下代码
if __name__ == "__main__":
    # 从用户输入读取一个整数
    n = int(input())
   
    # 检查输入是否为正整数
    if n < 1:
        print("必须输入正整数")
    else:
        # 调用 fun1 函数来计算质因数
        list_Z = fun1(n)
        # 将质因数列表转换为字符串并打印
        print( " ".join(map(str, list_Z)))

发表于 2024-10-04 16:45:16 回复(0)
提交观点

问题信息

排序
来自：2016乐视暑期实习生...
难度：
79条回答 123230浏览

热门推荐

通过挑战的用户

查看代码

相关试题

质数因子

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号