首页 > 试题广场 >

质数因子

[编程题]质数因子
  • 热度指数：1189878 时间限制：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)
奋斗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)
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)
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)
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)
天朗月明头像 天朗月明
#include<iostream>
using namespace std;
int main()
{
    int n=0;
    while(cin>>n)
    {
        int m=2;
        while(n>=m)
        {
            while(n%m)
                m++;
            cout<<m<<" ";
            n=n/m;
        }
    }
    return 0;
}
发表于 2016-12-15 19:51:26 回复(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)
马客(Mark)头像 马客(Mark)
我只想知道，什么叫做 “以空格隔开”？ 

#include <bits/stdc++.h>
using namespace std;

int main(){
    long long x;
    while(scanf("%lld", &x) == 1){
        if(x < 2) continue;
        //bool f = true;
        for(long long i = 2; i * i <= x; ++i) {
            while(x % i == 0){
            	//if(f) f = false;
            	//else putchar(' ');
                //printf("%lld", i);
                printf("%lld ", i);
                x /= i;
            }
        }
        if(x > 1) {
            //if(f) f = false;
            //else putchar(' ');
            //printf("%lld", x);
            printf("%lld ", x);
        }
        puts("");
    }
    return 0;
}

发表于 2016-05-11 13:03:06 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

质数因子

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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