首页 > 试题广场 >

质数因子

[编程题]质数因子

热度指数：1214931 时间限制：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$ 。

输入描述:

在一行上输入一个整数  代表待分解的整数。

输出描述:

在一行上从小到大输出若干个整数，代表  的质因子。

示例1

输入

输出

2 2 3 3 5

说明

在这个样例中，。

示例2

输入

输出

算法知识视频讲解

Python 3

牛客435747241号

n=int(input())

a=2

k=[]

if n<2:

k.append(n)

for i in range(2,int(n**0.5) +1):

while n % i ==0:

k.append(i)

n=n//i

if n>2:

k.append(n)

print(' '.join(map(str,k)))

发表于 2025-05-03 13:54:48 回复(0)

Python 3

牛客97190794号

num2 = eval(input())

def is_zhishu(num2):

if num2 > 5 and (num2 % 2 == 0 or num2 % 3 == 0 or num2 % 5 == 0):

return 'n'

else:

for i in range(2,int(num2 ** 0.5 + 1)):

if num2 % i == 0:

return 'n'

break

else:

return 'y'

def list_yinshu(num3):

ls2 = []

flg2 = is_zhishu(num3)

if flg2 == 'n':

for i in range(2,int(num3 ** 0.5 + 1)):

if num3 % i == 0:

ls2.append(i)

ls2.append(num3 // i)

break

return ls2

else:

return [num3]

ls4 = []

def list_zhiyinshu(ls3):

for i in ls3:

if is_zhishu(i) == 'y':

ls4.append(i)

else:

ls5 = list_yinshu(i)

list_zhiyinshu(ls5)

if is_zhishu(num2) == 'y':

print(list_yinshu(num2)[0])

else:

ls6 = list_yinshu(num2)

list_zhiyinshu(ls6)

for j in ls4:

print(j,end=' ')

发表于 2025-04-27 13:11:11 回复(0)

Python 3

牛客408176705号

a = int(input())

def isprime(n):
    if n == 2:
        return True
    for i in range(2,int(n**0.5)+1):
        if n%i == 0:
            return False
    return True

def prime(lim):
    for i in range(2,lim):
        if isprime(i):
            yield i

p = prime(a)

n = next(p)

while n<=a:
    if isprime(a):
        print(a)
        break

    if a%n == 0:
        a = a//n
        print(n,end=' ')
    else:
        n = next(p)

创建质数生成器，逐步输出质因数

发表于 2025-03-22 23:33:17 回复(0)

Python 3

牛客561054665号

a = int(input())

result = []

def count(a):

for i in range(2,a+1):

b = a % i

if b == 0:

result.append(i)

count(a//i)

break

else:

continue

count(a)

print(' '.join(map(str,result)))

说运行超时

发表于 2024-10-24 15:15:50 回复(0)

Python 3

喜欢吃火锅的奶糖offer多多

1. $n=a*b, {\exists} a, b \leq \sqrt{n}$

2. 相同的质因数全部除掉，则排除具有该质因数的合因数

3. 除掉所有的质因数后，剩下的不为1的数为其质因数

import math

while True:
    try:
        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 != 1:
            print(n)
    except:
        break

编辑于 2024-03-21 15:53:57 回复(0)

Python 3

渴望的迪恩

为啥不对呢，大佬解答一下

var = int(input())


def f():
    global var
    for i in range(2, var):
        while var % i == 0:
            print(i, end=' ')
            var = var // i
            f()


f()

编辑于 2024-03-08 19:19:27 回复(0)

Python 3

XMZ_LL

a = int(input())

def sub(num):
    if num % 2 == 0:
        return 2, num // 2
    else:
        i = 1
        while (2 * i + 1)*2 * i + 1 <= num:
            if num % (2 * i + 1) == 0:
                return 2 * i + 1, num // (2 * i + 1)
            i = i + 1
    return 0, num

s_list = []
s1, s2 = sub(a)
while s1 != 0:
    s_list.append(s1)
    s1, s2 = sub(s2)
if s2 > 1:
    s_list.append(int(s2))

print(' '.join(str(s) for s in s_list))

发表于 2024-01-15 14:33:07 回复(0)

Python 3

牛客Lorzen

import sys

strs = int(input())

k = 2

lis = []

s = strs

for i in range(0, strs):

y1 = int(s % k)

if y1 == 0:

s = int(s / k)

y1 = s

lis.append(k)

elif y1 != 0:

k += 1

if s == 1:

break

# print(lis)

s_new = ""

for i in lis:

s_new = s_new + str(i) + " "

print(s_new)

发表于 2023-11-15 17:15:51 回复(0)

Python 3

米米米米米饭

from math import sqrt

a = int(input())

for i in range(2,a)[:int(sqrt(a))+1]:

while a % i == 0:

print(i, end=' ')

a //= i

if a != 1:

print(a)

发表于 2023-08-04 23:33:13 回复(0)

Python 3

希望被offer砸中的小山竹很可爱

n=int(input())

flag=0

for m in range(2,594):

for k in range(4):

if n%m==0:

print(m,end=' ')

n=n/m

flag=flag+1

if flag==0:

print(n)

if flag!=0 and n>1:

print(int(n))

##面向答案编程

发表于 2022-12-04 17:23:17 回复(0)

Python 3

贰贰😈

def factor(N):
    res = []
    if N > 1:
        c = int(N**0.5)
        while N % c:
            c = c - 1
        if c == 1:
            res.append(int(N))  # int !!!!!
        else:
            res = res + factor(c)
            res = res + factor(N / c)

    return res


if __name__ == "__main__":
    N = int(input())
    res = sorted(factor(N))
    res = list(map(str, res))
    print(" ".join(res))

发表于 2022-11-18 14:37:51 回复(0)

Python 3

李达野

为什么质因子判断到平方根就可以了呢？

发表于 2022-09-06 22:16:53 回复(0)

Python 3

牛客524132996号

# 循环次数较多，有一组大数过不了

num = int(input())

while True:
for i in range(2,num+1):
if num % i == 0:
num = int(num/i)
print(i, end=" ")
break
if num == 1:
break

发表于 2022-08-29 21:35:37 回复(0)

Python 3

Aprilhahaha

import math
num = int(input())
prime = 2
s = ''
while prime < math.sqrt(num) + 1:
    if num%prime != 0:
        prime += 1
    else:
        num=num//prime
        s = s + str(prime) + ' '
s = s + str(num)
print(s)

发表于 2022-08-28 16:50:57 回复(0)

Python 3

牛客428544446号

num=int(input())
for i in range(2,int(num**0.5+1)):
while num%i==0:
print(i,end=' ')
num=num//i
if num!=1:
print(num)

发表于 2022-08-27 22:07:24 回复(0)

Python 3

牛客959453838号

num=int(input())
lst=[]
while num%2==0:
    lst.append(2)
    num=num//2
while num%3==0:
    lst.append(3)
    num=num//3
while num%5==0:
    lst.append(5)
    num=num//5
while num%7==0:
    lst.append(7)
    num=num//7
while num%17==0:
    lst.append(17)
    num=num//17
while num%13==0:
    lst.append(13)
    num=num//13
while num%23==0:
    lst.append(23)
    num=num//23
while num%107==0:
    lst.append(107)
    num=num//107
if num!=1:
    lst.append(num)
lst.sort
for j in lst:
    print(j,end=' ')

for i in range(7,num//30):

if num%i==0:

lst.append(i)

num=num//i

就一直提醒超时，对着答案一个一个写出来，就能全部通过啦

发表于 2022-08-22 22:21:27 回复(0)

Python 3

牛客719887639号

import math
def is_prime():
n = int(input())
loop = int(math.sqrt(n))+1
for i in range(2,loop):
while n % i == 0:
print(i,end=' ')
n = n // i
if n > 2:
print(n)
if __name__ == '__main__':
is_prime()

发表于 2022-08-22 03:19:11 回复(0)

Python 3

牛客762574969号

import math
x=int(input())
y=int(x**0.5+1)
z=[]
for i in range(2, y):
while x%i==0:
x=x/i
z.append(i)
if x!=1:
z.append(int(x))
if z:
for i in range(len(z)):
print(z[i],end=" ")
else:
print(x)

发表于 2022-08-20 09:16:35 回复(0)

提交观点

问题信息

排序

来自：2016乐视暑期实习生...

难度：

98条回答 8110收藏 123829浏览

通过挑战的用户

查看代码

spcire

2023-03-07 20:23:25
Media_Luhn

2023-02-02 23:55:15
牛客29761...

2023-01-24 12:08:15
帅阿衰

2023-01-07 14:37:29
牛客18173...

2022-12-02 16:24:57

质数因子

输入描述:

输出描述:

输入

输出

说明

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题