首页 > 试题广场 >

质数因子

[编程题]质数因子
  • 热度指数：1179260 时间限制：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^8 + 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)
丛林守望者头像 丛林守望者 
 public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
            long num = scanner.nextLong();
            if(num <= 3){
                System.out.println(num);
                continue;
            }
            for (int i = 2; i <= num; i++) {
                while (num % i == 0) {
                    System.out.println(i + " ");
                    num /= i;
                }
            }
        }
    }

发表于 2020-08-08 13:50:08 回复(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)
C/C++
小迷疯头像 小迷疯
不考虑质因子的，全都是耍流氓
贴个C的吧 
#include <stdio.h>

#define ARR_LEN 200
#define TABLE_LEN 10000
static char ans[ARR_LEN];
static long numTable[TABLE_LEN] = {2,};
static int numTableLen = 1;

char* getResult(long ulDataInput)
{
    int lenAns = 0;
    memset(ans,0,sizeof(char) * ARR_LEN);
    
    
    while(1 != ulDataInput)
    {
        while(0 == ulDataInput%numTable[numTableLen - 1])
        {
            int end = lenAns;
            long num = numTable[numTableLen - 1];
            
            ans[end] = ' ';
            end++;
            
            while(num)
            {
                ans[end] = num%10 + '0';
                num = num/10;
                end++;
            }
            
            for(int i = 0; i < (end - lenAns)/2; i++)
            {
                char tmp = ans[lenAns + i];
                ans[lenAns + i] = ans[end - 1 - i];
                ans[end - 1 - i] = tmp;
            }
            
            lenAns = end;
            
            ulDataInput /= numTable[numTableLen - 1];
        }
        
        if(ulDataInput > numTable[numTableLen - 1])
        {
            for(long i = numTable[numTableLen - 1] + 1; i <= ulDataInput; i++)
            {
                int flag = 1;
                for(int j = 0; j < numTableLen; j++)
                {
                    if(0 == i%numTable[j])
                    {
                        flag = 0;
                        break;
                    }
                }
                
                if(flag)
                {
                    numTable[numTableLen] = i;
                    numTableLen++;
                    break;
                }
            }
        }
    }
    
    ans[lenAns] = '\0';
    
    return ans;
}

int main()
{
    long n = 0;
    
    scanf("%d",&n);
    
    printf("%s\n",getResult(n));
    
    return 0;
}


编辑于 2020-04-14 10:29: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)
Python
Zoom内推助手头像 Zoom内推助手
效率贼高的Python 算法，其中有一句i=2我也没太明白，不过就是很***，有懂得大佬，望指点一二。 
n = int(input())
i = 2
ans = []
while i <= n:
    if n % i == 0:
        ans.append(i)
        n = n // i
        #非常妙，把i置为2。我也没想好怎么解释，有知道的大神望指点
        i = 2
        continue
    i += 1
for each in ans:
    print(each, end = ' ')

编辑于 2018-07-05 15:51:36 回复(2)
想成为一个优秀的人头像 想成为一个优秀的人

import java.util.Scanner;
//渣渣的我用渣渣的方法，比不上其他大神
public class Main {
    
public static void main(String[] args) {
    Scanner input = new Scanner(System.in);
    while(input.hasNext()) {
        System.out.print(getResult(input.nextLong()));
        }
    }
public static String getResult(long ulDataInput) {
    long divNum = 2;
    String result = "";
    while(divNum <= ulDataInput) {
        if(ulDataInput > 1 && (ulDataInput%divNum == 0)) {
            ulDataInput /=divNum;
            result = result+divNum+" ";
        }else {
            divNum++;
        }
        if(ulDataInput == 1)break;
    }
    if(result.length()==0)
        result = result+ulDataInput+" ";
    return result;
    
}


//利用Java判断一个数是否是素数的算法 
static boolean f(long a){ 
  boolean ean = true; 

  for(int i=2;i< Math.sqrt(a);i++){ //Math.sqrt 是调用Math类中的sqrt方法，求一个数的平方根
      if(a%i==0){ 
          ean = false; 
          break; 
          } 
  }
  return ean; 
}

}


发表于 2018-05-23 22:22:46 回复(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)
lanxuewei头像 lanxuewei 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader bufferedReader = new 
            BufferedReader(new InputStreamReader(System.in));
        Integer num = Integer.valueOf(bufferedReader.readLine());
        //System.out.println("num = " + num);
        for (int i = 2; i <= num; i++){
            if (num % i == 0){
                System.out.print(i + " ");
                num = num / i;      //重新赋值
                i = 1;              //重新遍历
            }
        }
        bufferedReader.close();
    }
}


编辑于 2017-09-15 13:58:24 回复(0)
NULL6666头像 NULL6666 
#include "bits/stdc++.h"
using namespace std;
int main()
{
    int n;
    while(cin>>n)
    {
        int temp=n;
        for(int i=2; i<=temp; i++)
        {
            while(n%i==0)
            {
                n/=i;
                cout<<i<<" ";
            }
        }
    }
}//复杂的解法


发表于 2017-09-13 22:51:14 回复(0)
妇科圣手头像 妇科圣手 
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        while (sc.hasNext()) {
            long num = sc.nextLong();
            System.out.println(getResult(num));
        }
    }
    
    private static String getResult (long n) {
    	int a = 2;
    	StringBuffer sb = new StringBuffer();
    
    	while (a * a <= n) {
        	while (n % a == 0) {
            	sb.append(a);
            	sb.append(" ");
            	n = n/a;
        	}
        	a++;
    	}
        // 如果是质数，那就是其本身
        if (n > 1) {
            sb.append(n);
            sb.append(" ");
        }
        return sb.toString();
    }
}

发表于 2017-07-05 20:09:37 回复(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)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

质数因子

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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