我要招人

去企业版

首页 > 试题广场 >

质数因子

[编程题]质数因子

热度指数：1101116 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

功能:输入一个正整数，按照从小到大的顺序输出它的所有质因子（重复的也要列举）（如180的质因子为2 2 3 3 5 ）

数据范围： $1 \le n \le 2 \times 10^{9} + 14 \$

输入描述:

输入一个整数

输出描述:

按照从小到大的顺序输出它的所有质数的因子，以空格隔开。

示例1

输入

输出

2 2 3 3 5

算法知识视频讲解

推荐

钉子

#include <iostream>

using namespace std;

int main(void)
{
    long input;
    //cin >> input;
    while (cin >> input)
    {
        while (input != 1)
        {
            for (int i = 2; i <= input; i++)
        	{
            	if (input % i == 0)
            	{
             	   input /= i;
             	   cout << i << ' ';
            	    break;
            	}
        	}
        }
        
    }
	
    
    
    return 0;
}

编辑于 2019-02-12 20:22:30 回复(102)

Python

SualLuhn

import math

num = int(input().split()[0])
z_list = []
for i in range(2,int(math.sqrt(num))+1):
    while num%i == 0:
        z_list.append(i)
        num = num//i
if num != 1:
    z_list.append(num)
for i in sorted(z_list):
    print(i,end=" ")

编辑于 2023-02-03 00:01:16 回复(0)

Python

牛客57287850号

def ff(a):
while True:
try:
i=2
while a%i!=0 and i<=a**0.5:
i+=1
if i>a**0.5:
print(int(a),end=' ')
break
else:
print(i,end=' ')
a=a/i
except:
break
if __name__ == '__main__':
a=int(input())

ff(a)

本题的关键是学会用数学的方法解题，循环到a**0.5即可，节省时间

m>n>1,(n为大于1的最小整数)

m*n=x（m、n为x的质数因子，n最小）

得：m=x/n

m>n

即 x/n>n

x>n**2

发表于 2021-07-13 09:52:08 回复(0)

Python

紧张的丹尼尔觉醒了

n = int(input())
i = 2
while i < (n**0.5) + 1:
if n % i == 0:
print(i,end=' ')
n = n/i
i = 2
else: i += 1
if n > 1:
n = int(n)
print(n,end=' ')

发表于 2021-07-03 07:41:07 回复(0)

Python

牛客237884401号

python2 解法：

import math

def func():
a = ''
num = int(input())
for i in range(2, int(math.sqrt(num))+1):
#print (math.sqrt(num))
while num % i == 0:
a = a+ str(i)+ ' '
num = num // i

if num != 1:
print a + str(num) + ' '
return
print a

if __name__ == "__main__":
func()

编辑于 2021-06-26 12:55:35 回复(0)

Python

牛客中的布努利

num = int(input())
if num ==1 :
    print(num)
else:
    i = 1
    while i < num**0.5+1:
        i = i+1
        if num % i == 0:
            print(i,end=' ')
            num = int(num/i)
            i -= 1
    if num != 1:
        print(num, end=' ')

编辑于 2021-06-19 20:20:53 回复(0)

Python

YizhuoYu

num = int(input())
fac = []
if num>=2:  #如果输入为1，则没有质因子。所以只需要考虑输入大于等于2.
    i=2;
    while i<= int(num**0.5)+1: # 对于输入num，我们只需要搜索至m，使得m^2>=num。再往后仍无质因子说明num本身就是最后一个质因子。
        if num%i == 0:
            fac.append(i)
            num = num/i # 找到一个质因子后即可减小num。
        else:
            i+=1
fac.append(int(num))
for i in fac:
    print(i,end=" ")

发表于 2021-06-18 12:49:22 回复(0)

Python

Victor丶

n = int(input())
i = 2
def func(a,b):
for i in range(b, int(a**0.5+1)):
if a%i == 0:
print(i, end=' ')
func(a//i, i)
break
else:
print(a, end=' ')
func(n,2)

发表于 2021-05-12 17:31:08 回复(0)

Python

牛客诶谁

import sys


def func(num):
    # 从2开始
    a = 2
    # 当num小于a的平方时，退出循环
    while num >= a**2:
        # 如果num%a为0，说明a是num的质因数，将num//a的结果重新赋值给num
        if num%a == 0:
            num = num//a
            print(a, end=' ')
        else:
            # 余数不为0，a加1，继续查找
            a += 1
    # 最后的num，也是质因子的一部分
    print(num, end=' ')

func(int(input()))

发表于 2021-05-05 22:14:15 回复(0)

Python

少年二师兄

N = int(input())
i = 2
while i * i <= N:
    while N % i == 0:
        print(i, end=" ")
        N = N // i
    i += 1
else:
    if N != 1:
        print(N, end=" ")

发表于 2021-04-22 10:57:18 回复(0)

Python

孤行ZGT

Python3不超时
图片说明

num = int(input())
i = 1
#终止条件：当迭代的num是质数时。
while i*i < num:  
    i += 1   #i从2开始，每迭代一次i加1
#当i为num的质数因子时，输出i，让num除以i，并把i减1，因为i可能还是因子
    if num%i == 0:  
        print(i, end=' ')
        num = int(num/i)
        i -= 1
print(num, end=' ')

发表于 2021-04-07 23:07:44 回复(3)

Python

牛客711829466号

#尽力了，想不到怎么化简了。。。根本过不了

import sys

maxnuml = 2*3*5*7*11*13*17
for line in sys.stdin:
    num = int(line)
    if num < maxnuml:
        numlist = [True] * num
    else:
        numlist = [True] * maxnuml
    # 把偶数单独抽出来减少计算时间长度
    i = 2
    for j in range(i, len(numlist), i):
        numlist[j-1] = False
    while num % i == 0:
        num = num // i

print('%d '%i, end='')

# 偷鸡

if num > maxnuml * 2:
print('%d '%num, end='')

continue

# 偷鸡结束

    i = 3
    while i <= num:
        if i < maxnuml:
            if numlist[i-1] == True:
                for j in range(i, len(numlist), i):
                    numlist[j-1] = False
                while num % i == 0:
                    num = num // i
                    print('%d '%i, end='')
            i += 2
        else:
            tempi = i % maxnuml
            if numlist[tempi] == True:
                while num % i == 0:
                    num = num // i
                    print('%d '%i, end='')
            i += 2
    if num == i-2:
        print('%d '%num, end='')

发表于 2021-03-29 20:00:56 回复(0)

Python

白可乐

def functions(s):
    result = ""
    
    len_s = s
    for i in range(2,len_s ):
#             a = s//i
        while(s%i==0):
            result = result +"%s "%(i)
            s=s/i
            
    if result == "":
        print("%s "%s)
    else:
        print(result)

为什么这样些竟然通过不了？

发表于 2021-03-24 14:12:35 回复(0)

Python

Bruce_xu

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

发表于 2021-03-23 14:22:55 回复(0)

Python

爱吃饭团.Deus

number=int(input())
for i in range(number-1,0,-1):
    if number%i==0 and i!=1:
        print(number//i,end=' ')
        number=i
    if i==1:
        print(number,end=' ')

发表于 2021-03-13 16:01:23 回复(1)

Python

东风雪


if __name__ == '__main__':
    a = int(raw_input())
    s= ''
    
    for i in xrange(2,a+1) :
        if i*i > a:
            if a == 1:
                break
            else:
                s=s+str(a)+' '
                break
        while a%i == 0:
            if a==1:
                break
            a= a/i
            s=s+str(i)+' '
    if s=='':
        print str(a)+' '
    else:
        print s

原来用range（）老是内存溢出，后面看了答案，发现xrange（）可以省内存就过了，以后都用xrange吧

发表于 2021-03-12 14:59:48 回复(0)

Python