首页 > 试题广场 >

质数因子

[编程题]质数因子

热度指数：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$ 。

输入描述:

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

输出描述:

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

示例1

输入

输出

2 2 3 3 5

说明

在这个样例中，。

示例2

输入

输出

算法知识视频讲解

文的盲

发表于 2021-01-17 14:00:05

此题，如果代码的最坏时间复杂度是线性的，只能通过大概 91% 的样例（我使用 java 的测试结果），原因之所在就是会有超大素数作为特殊样例来恶心人： public static void main(String[] args) { Scanner scanner = new Scanner 展开全文

牛客969573159号

发表于 2021-09-22 11:25:51

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: 展开全文

大磊子

发表于 2022-02-28 15:57:51

大多数同学只关注到了一开始的时候使用平方根降低复杂度，然而忽略了后续进一步的优化，假如测试用例加上2的1000次方会如何？使用while循环会比使用for循环时间复杂度要低，for循环的条件在循环中是不可变化的，而while循环每一次都可以重新调整条件缩小范围（如果条件有变化），从而这个时间复杂度展开全文

风格化_asd

发表于 2020-01-02 18:39:22

题目描述功能:输入一个正整数，按照从小到大的顺序输出它的所有质数的因子（如180的质数因子为2 2 3 3 5 ）最后一个数后面也要有空格详细描述：函数接口说明： public String getResult(long ulDataInput) 输入参数：long ulDataInput：输入展开全文

f(x)=n^2

发表于 2021-09-27 20:28:57

import math n = int(input()) for i in range(2, int(math.sqrt(n))+1): # 一个数可以被它所有的质因子表示 # 这里仅考虑不大于根号下n的因子 # 因为当n被所有不大于根号下n的【质】因子整除后，要么余1，要么余2，展开全文

hello1huan

发表于 2020-01-19 17:22:25

import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner scan = new Scanner(System.in); long 展开全文

小海亦狂

发表于 2021-02-15 20:11:53

def func(): num = int(input()) def getprime(n): &nb 展开全文

东北牧码人

发表于 2022-02-12 01:35:22

我们尽量减少循环，这样就能减少时间复杂度 public class Main{ public static void main(String[] args) { // 处理输入 Scanner sc = new Scanner(System.in); 展开全文

海森堡-

发表于 2022-01-25 18:14:29

【提供一个简易答案】耗时3MS #include<stdio.h> #include<math.h> int main(viod) { int a, b, i = 0; scanf("%d", &a); for (b = 2; b < 展开全文

Sunshine148

发表于 2021-01-26 11:50:01

解题思路这题有点恶心啊。分解质因数，从最小的开始不停除法，除到为1。或者，除到最后除不了，就输出自己。有两个坑。第一个就是这个数本身是个质数。第二就是可能会超时，除到它的平方值即可。还可以判断下除数是不是质数，但是呢，没必要，因为会增加判断的次数，得不偿失。 #include<stdio. 展开全文