首页 > 试题广场 >

质数因子

[编程题]质数因子
  • 热度指数：1216714 时间限制：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
算法知识视频讲解
添加回答
Python 3
BoyangXu头像 BoyangXu
a = int(input())  # 可以测试 5432542544444213399，18446744073709551616
i = 2
b = int(a ** 0.5)
while i <= b:
    while a % i == 0:
        a = int(a / i)
        b = int(a ** 0.5)
        print(str(i), end=' ')
    i += 1
if a != 1:
    print(str(a), end=' ')
发表于 2021-08-11 17:10:02 回复(0)
Java
暮霞落清渊头像 暮霞落清渊
import java.util.*;
import java.io.*;
public class Main {
    /*
    既是质数又是因子
    */
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = "";
        while ((str = br.readLine()) != null) {
            long n = Long.parseLong(str);
            String res = getStr(n);
            System.out.println(res);
        }
    }
    // 获取输出格式
    public static String getStr(long num) {
        String ret = "";
        for(int i = 2; i*i <= num; i++) { // 求质数
            while (num % i == 0) {// 求因子
                ret += i + " ";
                num /= i;
            }
        }
        if (num != 1) ret += num + " ";
        return ret;
    }
}
发表于 2021-07-16 17:29:51 回复(0)
冷小子波波头像 冷小子波波
import java.util.Scanner;
public class Main
{
    public static void main(String[] args)
    {
        Scanner  s = new Scanner(System.in);
        while(s.hasNextLong()){
            long num = s.nextLong();
            for(int i = 2;i<=num;i++){
                if (num%i==0){
                    System.out.print(i+" ");
                    num/=i;
                    i=1;
                }
            }
        }
    }
}
发表于 2020-08-31 21:02:31 回复(1)
Java
漏墨小子头像 漏墨小子 
public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        long s = sc.nextLong();
        int temp = 2;
        StringJoiner str= new StringJoiner(" ");
        while(temp<=s){
            if(s%temp==0){
            	if(temp==s){
                    str.add(temp+"");
                    break;
                }else{
                    str.add(temp+"");
                    s=s/temp;
                }
            } else {
            	temp++;
            }
        }
    }
这个 是啥问题
发表于 2020-08-18 21:30:33 回复(0)
奋斗ing_QT头像 奋斗ing_QT 
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    while(cin>>n){
        int sh = n;//被除数
        int ch = 2;//除数
        while(sh!=1){
            if(sh % ch==0){
                cout << ch << ' ';
                sh /= ch;
            }
            else ++ch;
        }
    }
    return 0;
}
    😑简单地判断即可
发表于 2020-06-23 15:41:15 回复(0)
Python
朝夕_头像 朝夕_ 
while True:
  try:
    a = int(input())
    b = []
    #从2开始寻找质数因子
    for i in range(2,a//2 + 1):
      while a%i ==0:
        a = a/i
        b.append(i)
    if b == []:
      b.append(a)
    for j in b:
      print(j,end = " ")
  except:
    break

发表于 2020-02-15 21:02:02 回复(1)
Python
Nicholas666头像 Nicholas666
a = int(input())
Outlist = []
for i in range(2, a // 2 + 1):
#for i in range(2, int(math.sqrt(a)) + 1):
    while a % i == 0:
        a = a / i
        Outlist.append(i)
print(" ".join(map(str, Outlist)) + " " if Outlist else str(a) + " ")

此题的关键是找出所有质数因子，而且每个质数因子可能有多个
发表于 2019-08-31 10:31:30 回复(0)
Tendō·Pein头像 Tendō·Pein
高票答案没有忽略了题目要求的字符串转化...
#include <iostream>
#include <string>
#include <vector>

using namespace std;
int hex2dec(string s);
string getResult(long ulDataInput);
string myitoa(long a);

int main(){
    long str;
    string a;
    while (cin >> str)
        cout << getResult(str);
    return 0;
}
string getResult(long ulDataInput)
{
    string str = "";
    char a[100];
    for (int i = 2; i <= ulDataInput; )
    {
        if ((ulDataInput%i) == 0)
        {
            ulDataInput /= i;
            str += myitoa(i);
            str += " ";
        }
        else
            i++;
    }
    return str;
}
string myitoa(long a)
{
    string str="";
    vector<int> nums_r;
    vector<int> nums;
    while (a)
    {
        nums_r.push_back(a % 10);
        a /= 10;
    }
    for (auto i = nums_r.end()-1;i>nums_r.begin();i--)
        nums.push_back(*i);
    nums.push_back(nums_r[0]);
    for (int i : nums)
    {
        switch (i)
        {
        case 0: str += "0"; break;
        case 1: str += "1"; break;
        case 2: str += "2"; break;
        case 3: str += "3"; break;
        case 4: str += "4"; break;
        case 5: str += "5"; break;
        case 6: str += "6"; break;
        case 7: str += "7"; break;
        case 8: str += "8"; break;
        case 9: str += "9"; break;

        default:
            break;
        }
    }
    return str;
}

发表于 2018-07-07 21:30:52 回复(0)
Java
tapakkur头像 tapakkur
//package com.gulamjan.t021.华为质数因子;
import java.util.Scanner;
public class Main {
 public static void main(String[] args) {
  // TODO Auto-generated method stub
  Scanner in = new Scanner(System.in);
  while (in.hasNext()) {
   long n = in.nextLong();
   System.out.println(getPrimeString(n));
  }
  in.close();
 }
 //判断 n 是否是个质数
 public static boolean isPrimeNumber(long  n) {
  boolean flag = true;
  for (int i = 2; i <= Math.sqrt(n); i++) {
   if (n % i == 0) {
    flag = false;
    break;
   }
  }
  return flag;
 }
 //获取符合要求的因子字符串
 public static String  getPrimeString(long n) {
  long temp = n;
  String string = "";
  for (int i = 2; i <= temp; i++) {
   if (isPrimeNumber(i)) {
    while(n % i == 0){
     string += i+" ";
     n = n / i;
    }
   }
  }
  return string;
 }
}
发表于 2017-10-05 16:42:04 回复(0)
QiLuYa头像 QiLuYa 
#include <stdio.h>
#include <string.h>

#define   N  100

int main()
{     long i;     int j;     long n;     char over;     long devisor[N];     scanf("%ld", &n);     j = 0;     while(1){         over = 1;         for(i=2 ; i<=(n+1)/2 ; i++){             if(n%i == 0){                 devisor[j++] = i;                 n /= i;                 over = 0;                 break;             }         }         if(over) break;     }          for(i=0 ; i<j ; i++){         printf("%ld ", devisor[i]);     }     printf("%ld \n", n);      }

编辑于 2017-09-17 10:54:27 回复(0)
zgh1992头像 zgh1992
#include <iostream>
#include <math.h>
using namespace std;

int prime(int k)
{
    int i;
    for(i=2;i<=sqrt(k);i++)
        if(k%i==0)
            return 0;
    return 1;
}

int main()
{
    long n,a[30];
    cin>>n;
    
    int i,j=0;
    
    for(i=2;n>1;)
    {    if(prime(i))
        {
            if(n%i==0)
            {
                a[j++]=i;
                n=n/i;    
            }
            else
                i++;
        }
        else 
            i++;
    }       
      
    for(i=0;i<j;i++)
        cout<<a[i]<<' ';
}
发表于 2017-06-09 16:10:31 回复(0)
杨浩哈哈头像 杨浩哈哈
#include <iostream>
using namespace std;
int main()
{
    long number,remainder=0,divisor=2;
    cin>>number;
    while(divisor<=number)
    {
        remainder=number%divisor;
        if(remainder==0)
   {
         number=number/divisor; 
            cout<<int(divisor)<<" ";
        }
        else
        {
        divisor++;    
        }
    }
}
发表于 2017-05-23 16:24:00 回复(0)
HelloWorldn头像 HelloWorldn
按理说行尾是不可以有空格的，这道题的行尾以空格结束，题目中也没有说明，感觉题目出的很不好。
发表于 2017-01-21 17:14:22 回复(0)
小珂椰子皮头像 小珂椰子皮 
import java.util.Scanner;

public class Main {
public static void main(String args[]){
	Scanner sc=new Scanner(System.in);
	while(sc.hasNext()){
      long a=2;
      long b=sc.nextLong();
      double c=b/a;
      if(c==1.0000)
    	  System.out.print(c);
      while(c!=1.000000){
    	  
    	  if(b%a==0){
    		  System.out.print(a+" ");
    		  b=b/a;
    	  }else{
    		  a++;
    	  }
    	  c=b;
      }
    
	}
}
}

发表于 2016-08-20 10:18:22 回复(0)
longyin头像 longyin 
import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner=new Scanner(new BufferedInputStream(System.in));
		while (scanner.hasNext()) {
			int num=scanner.nextInt();
			int i=2;
			while (num>1) {
				if (num%i==0) {
					System.out.print(i+" ");
					num/=i;
					i=2;
				}else {
					i++;
				}
			}
		}
	}

}
//运行时间：24ms
//占用内存：276k

发表于 2016-08-02 13:18:35 回复(3)
云中鸟头像 云中鸟
#include<iostream>
using namespace std;
int main()
{
    float num;
    while(cin>>num)
    {
        int num1=(int)num;
        float num2=num-num1;
        if(num2>=0.5)
        {
num1=num1+1;            
        }
        
        cout<<num1<<endl;
    }
    return 0; 
}

发表于 2016-05-03 09:50:33 回复(0)
Python3
牛客885638482号头像 牛客885638482号
def a(m):
    k =0
    for i in range(2,m):
        if m%i ==0:
            k+=1
            break
    if k >0:
        return i,m//i
    else:
        return m
def b(n):
    t =a(n)
    if n ==t:
        print(n,end=' ')
    else:
        for i in t:
            b(i)
b(int(input()))
            
发表于 2022-06-08 15:21:26 回复(0)
Java
牛客210097429号头像 牛客210097429号
import java.util.*;
public class Main{
    public static void getPrimer(long num){
        long sqrNum=(long)Math.sqrt(num);
        for(int i=2;i<=sqrNum;i++){
            if(num%i==0){
                System.out.print(i+" ");
                getPrimer(num/i);
                break;
            }
            if(i==sqrNum){
                System.out.print(num+" ");
            }
        }
    }
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        long num=in.nextLong();
        getPrimer(num);
    }
}
取根号num作为比较总次数来避免大质数超时，递归思想
发表于 2022-01-08 13:53:00 回复(1)
Python
华科平凡头像 华科平凡 


a, res = int(input()), []
for i in range(2, a // 2 + 1):
    while a % i == 0:
        a = a / i
        res.append(i)
print(" ".join(map(str, res)) + " " if res else str(a) + " ")
编辑于 2018-07-17 21:15:23 回复(78)
Java
牛客330571410号头像 牛客330571410号
/**
其实这就是小数数学学的那个东西。

1.  判断一个数是否为质数：除去1和本身之外  没有其他约数
    比如： 2 3 5 7 11 13 这种都是质数。

2.  题目给出一个数，求它的质因子。
    所以首先这个数必须是它的因数，其次是质数。

3.  求一个数的质数，只需要判断到它的平方根位置即可。

4.  然后排序。
    从最小2的开始处理，找到之后进行排序，自然就排好了序。
 
**/

发表于 2022-03-17 21:30:54 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

质数因子

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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