首页 > 试题广场 > 质数因子
[编程题]质数因子

功能:输入一个正整数,按照从小到大的顺序输出它的所有质数的因子(如180的质数因子为2 2 3 3 5 )

最后一个数后面也要有空格

详细描述:


函数接口说明:

public String getResult(long ulDataInput)

输入参数:

long ulDataInput:输入的正整数

返回值:

String




输入描述:

输入一个long型整数



输出描述:

按照从小到大的顺序输出它的所有质数的因子,以空格隔开。最后一个数后面也要有空格。

示例1

输入

180

输出

2 2 3 3 5

625个回答

添加回答
推荐
#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 回复(59)


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 回复(24)
再简洁不过的C++的方式,共三种方法:

#include <iostream>
#include <math.h>
using namespace std;

int main()
{
	long int input;

	//方法一
	//while (cin >> input)
	//{
	//	while (input != 1)
	//	{
	//		for (int i = 2; i <= input; i++)
	//		{
	//			if (input % i == 0)
	//			{
	//				input /= i;
	//				cout << i << ' ';
	//				break;  //只要能被i整除,i总是从2开始
	//			}
	//		}
	//	}

	//}

	//方法二
	//while (cin >> input)
	//{
	//	for (int i = 2; i <= input; i++)
	//	{
	//		//只要能被i整除,i总是从2开始
	//		if (input%i == 0)
	//		{
	//			input /= i;
	//			cout << i << " ";
	//			i = 1;//经i++之后 i又变为2开始
	//		}
	//	}
	//}

	//方法三
	while (cin >> input)
	{
		for (int a = 2; a<= sqrt(input); a++)
		{
			//此处是while,把a整除结束才可加1
			while (input%a == 0)
			{
				cout << a << ' ';
				input = input / a;
			}
		}
		if (input>1) cout << input << ' ';
	}

	//system("pause");
	return 0;
}

编辑于 2016-07-04 21:47:33 回复(5)
好多人没明白这个问题的意思,其实就是让你把输入的整数因式分解,只不过因子必须都是质数
例如:180 = 2 * 2 * 3 * 3 * 5;90 = 2 * 3 * 3 * 5;而不是找出所有的质数因子


import java.util.Scanner;

public class Main
{
	public static void main(String[] args)
	{
		Scanner scanner = new Scanner(System.in);
		
		long number = 0;
		
		while(scanner.hasNextLong())
		{
			number = scanner.nextLong();
			isPrimerFactors(number);
		}
		
	}
	
	private static void isPrimerFactors(long num)
	{
		long number = num;
		while(number != 1)
		{
			for(int i = 2; i <= number ;i++)
			{
				if(number % i == 0)
				{
					number /= i;
					System.out.print(i + " ");
					break;
				}
			}
		}
	}
}


发表于 2016-07-27 10:25:09 回复(18)
#include <iostream>
using namespace std;

int main()
{
    long num;
    
    while(cin >> num){
        if(num == 1){
            cout << num << endl;
            continue;
        }
        
        for(int i = 2; i <= num; ++i){
           if(num%i == 0){               
               num = num/i;
               cout << i << " ";
               i--;//遇到一个质数,那么该质数可能会被整除多次
           }           
    	}
        cout << endl;        
    }    
    
    return 0;
}

发表于 2016-07-22 22:37:50 回复(2)
//利用回归简单一些
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while(scan.hasNext()){
            long num = scan.nextLong();
            canculate(num);
        }
    }
    public static void canculate(long num){
        for(long i=2;i<=num;i++){
            if(num%i==0){
                System.out.print(i+" ");
                canculate(num/i);
                return;
            }
        }
    }    
}

发表于 2018-03-11 21:56:30 回复(1)
import sys

while True:
    try:
        number = long(sys.stdin.readline())
        i = 2

        while number != 1:
            while number % i == 0:
                print i,
                number = number / i
            i = i + 1
        print "",
    except:
        break
感谢嘻嘻女神曾经给我的鼓励!

编辑于 2016-08-05 19:57:15 回复(3)
#include <iostream>
using namespace std;
int main()
{
    long n;
    while(cin>>n)
    {
        for(int i = 2;i <= n;i++)//从2开始
        {
            while(n%i==0)//每找到一个因数,除尽为止。找到的因数一定是质数
            {
                cout<<i<<' ';
                n /= i;
            }
        }
    }
}

发表于 2017-08-14 16:29:57 回复(3)
import java.util.Scanner;
public class PrimeFactor{
    public static void main(String[]args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            long l = in.nextLong();
            System.out.print(getResult(l));
        }
    }
    static String getResult(long ulDataInput){
        StringBuilder str = new StringBuilder();
        if(ulDataInput <= 1)
            return "请输入大于1的正整数";
        while(ulDataInput != 1){
            for(int i = 2;i <= ulDataInput;i++){
                if(ulDataInput % i == 0){
                    str.append(i + " ");
                    ulDataInput = ulDataInput / i;
                    break;
                }
            }           
        }
        return str.toString();
    }
}


发表于 2016-07-13 23:07:26 回复(8)
#include <stdio.h>

int main(void)
{
    long int a;
    int i;
    printf("Input a positive number:a\n");
    scanf("%d",&a);
    
    for (i=2;i<=a;i++)
    {    
     while (a != i)
        {
        if (a%i == 0)
            {
                printf("%d ",i);
                a = a/i;
            }
            else
                break;
        }
    }
    printf("%d ",a);
    printf("\n");
    return 0;    
}
发表于 2016-08-30 15:07:46 回复(1)
//阿西吧,JS调半天说我输入有错误,原来最后一个数要接空格,搞得我特意trim了一下
var readline = require("readline");
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});
var n;
var i;
var j;
var raw = [];
raw[0] = 2;
rl.on('line', function(line) {
    n = parseInt(line.trim());
    for (i = raw[raw.length - 1] + 1; i <= n; i++) {
        for (j = 0; j < raw.length; j++) {
            if (i % raw[j] === 0) break;
        }
        if (j === raw.length) raw.push(i);
        else continue;
    }
    var result = [];
    for (i = 0; i < raw.length; i++) {
        while (n % raw[i] === 0) {
            n = n / raw[i];
            result.push(raw[i]);
            result.push(" ");
        }
    }
    result = result.join("");
    console.log(result);
});

发表于 2016-08-08 01:46:01 回复(0)
/*需要注意的是输出的最后一个质数因子也需要以空格结束*/
#include<iostream>

using namespace std;

void trial_divisio_fac(int n){
	int a=2;
	while(a*a<=n){
	    while(n%a==0){
	        cout<<a<<' ';
	        n=n/a;
	    }
	    a++;
	}
	if(n>1) cout<<n<<' ';
}
int main(){
	int n;
	cin>>n;
	trial_divisio_fac(n);
	return 0;
}

发表于 2016-03-30 23:06:21 回复(1)
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        long data = sc.nextLong();
        for (int i = 2; i < data + 1; i++) {
            while (data % i == 0) {
                System.out.print(i + " ");
                data = data / i;
            }
        }
    }
}

发表于 2018-03-02 19:34:35 回复(1)
#include <iostream>
#include <string>
#include <sstream>
#include <stdio.h>
using namespace std;
int main()
{
    long ulDataInput;
    //scanf("%ld",&ulDataInput);
    while(cin>>ulDataInput)
    {
        string result;
        stringstream ss;
        long tempData;
        for(int i=2;i<=ulDataInput;i++)
        {           
            while(!(tempData=ulDataInput%i))
            {
                ss<<i<<' ';
                ulDataInput=ulDataInput/i;
            }

        }
        getline(ss,result);
        //result.pop_back();
        cout<<result<<endl;
        //printf("%s\n",result.c_str());
        //system("PAUSE");
    }   
	return 0;
}

发表于 2016-07-07 21:04:00 回复(0)
//返回string类型,需要处理一下
#include <iostream>
#include <string>
#include <sstream>
using namespace std;

string getResult(long ulDataInput);
bool IsPrinumber(int value);
int main()
{
	long data;
	cin >> data;
	string str = getResult(data);
	string substr = str.substr(0,str.length()-1);
	cout << str << endl;
	return 0;
}
string getResult(long ulDataInput)
{
	string result="";
	if (ulDataInput>1)
	{
		for (int i=2;i<=ulDataInput;i++)
		{
			if (0 == ulDataInput%i)
			{
				if (IsPrinumber(i))
				{
					stringstream s;
					s<<i;
					result +=s.str();
					result += " ";
					ulDataInput = ulDataInput/i;
					break;
				}
			}
		}
		result = result+getResult(ulDataInput);
	}
	return result;
}
bool IsPrinumber(int value)
{
	bool flag = true;
	for (int j=2;j<value;j++)
	{
		if (0 == value%j)
		{
			flag =false;
			break;
		}
	}
	return flag;
}

发表于 2016-03-24 16:57:13 回复(0)
s = eval(input())
while(s != 1):
    i = 2
    while True:
        if(s % i == 0):
            print(i, end = ' ')
            s = s / i
            break
        i = i + 1

发表于 2017-07-15 14:14:21 回复(1)
题目并没有说输入有多组测试用例! 而且输出的最后一个因子后面为什么还会有空格?
发表于 2016-08-03 23:14:19 回复(1)
#include<iostream>
using namespace std;
int main(){
    int num;
    cin>>num;
    for(int i=2;i<=num;i++){
if(num%i==0){
num/=i;
cout<<i<<" ";
i=1;
}
}
}

发表于 2016-04-29 16:15:10 回复(1)
import java.util.ArrayList;
import java.util.Scanner;

/*
 * 质数因子
 */
public class Main {

    public String getResult(long ulDataInput) {
        ArrayList<String> list = new ArrayList<String>();
        while(ulDataInput % 2 == 0) {
            ulDataInput /= 2;
            list.add("2");
            list.add(" ");
        }
        
        for(int i = 3;i<= Math.sqrt(ulDataInput);i += 2) {
            while(ulDataInput % i == 0) {
                ulDataInput /= i; 
                list.add(String.valueOf(i));
                list.add(" ");
            }
        }
        
        if(ulDataInput > 2) {
            list.add(String.valueOf(ulDataInput));
            list.add(" ");
        }
        String s = "";
        for(String j : list) {
            s += j;
        }
        return s;
    }
    public static void main(String[] args) {
        
        Scanner in = new Scanner(System.in);
        long x = in.nextLong();
        Main ma = new Main();
        System.out.println(ma.getResult(x));
    }

}

 
编辑于 2018-08-24 19:09:18 回复(0)
//第一次用递归解决了问题,纪念一哈
#include<stdio.h>
int z(long);//判断质数 int z(long a)
{
    for(int i=2;i<a;i++)
    {
        if(a%i==0)
            return 0;
    }
    return 1;
}
void y(long);//递归找因子
void y(long a)
{
    int k=2;
    while(a%k!=0&&k<a){
         k++;
    }
    if(z(k)==1) printf("%d ",k); 
    if(k<a) y(a/k);
}
int main()
{
    long x;
    while(scanf("%d",&x)!=EOF){
        y(x);
    }
    return 0;
}

编辑于 2018-08-18 17:00:12 回复(0)
  • 从2开始遍历,如果可以被2整除,即改变n=n/2,
  • 在遍历的过程中不需要判断该因子是否是质数,因为如果n不能被2整除,那一定不能被2的倍数整除。
  • 在遍历的过程中n会越来越小,循环上限也会越来越小,所以该算法,效率比较高。
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        for (int i = 2; i <= n; i++) {
            while (n % i == 0) {
                n /= i;
                System.out.print(i + " ");
            }
        }
    }
}
编辑于 2018-08-08 15:18:37 回复(0)

扫一扫,把题目装进口袋

牛客网,程序员必备求职神器

扫描二维码,进入QQ群

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