首页 > 试题广场 >

质数因子

[编程题]质数因子
  • 热度指数:1086220 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

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


数据范围:

输入描述:

输入一个整数



输出描述:

按照从小到大的顺序输出它的所有质数的因子,以空格隔开。

示例1

输入

180

输出

2 2 3 3 5
推荐
#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 回复(102)
不超时的java:
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner scan =new Scanner(System.in);
        Long num=scan.nextLong();
        for(int i=2;i<=(int)(Math.sqrt(num)+1);i++){
            while(num%i==0){
                System.out.print(i+" ");
                num=num/i;
            }
        }
        if(num>2) System.out.print(num+" ");
    }
}
发表于 2022-03-19 17:16:56 回复(0)

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc= new Scanner(System.in);
        int num= sc.nextInt();
        for(int i=2;i<=Math.sqrt(num);i++){
            if(num%i==0){
                 System.out.print(i+" ");
                num=num/i;
                i=1;
            }
            continue;
        }
        System.out.print(num+" ");
    }
}
发表于 2021-11-02 19:57:42 回复(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();
            long num2 = (long)Math.sqrt(num);
            for(int i = 2; i <= num2; i++){
                while(num % i == 0){
                    num /= i;
                    System.out.print(i + " ");
                }
            }
            System.out.println(num == 1 ? "" : num + " ");
        }
        sc.close();
    }
}

发表于 2021-08-16 18:53:16 回复(0)
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)
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.*;
public class Main
{
    public static void main(String[] args) 
    {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()) 
        {
            long n = in.nextLong();
            for(int i = 2; i <= Math.sqrt(n); i++)
            {
                while(n % i == 0) 
                {
                  System.out.print(i);
                  System.out.print(" ");
                  n /= i;               
                 }  
            }
            if(n > 1) 
            {
               System.out.print(n);
               System.out.print(" "); 
            }
            
        }
    }
}

发表于 2021-06-01 17:09:53 回复(0)
#include <iostream>

using namespace std;

int main(void)
{
    long a;
    int last_base = 3;
    while (cin>>a)
    {
        while (a % 2 == 0)
        {
            cout<<"2 ";
            a = a / 2;
        }
        while (a >= last_base)
        {
            for (int i = last_base; i <= a; i = i + 2)
            {
                if (a % i == 0)
                {
                    last_base = i;
                    cout<<i<<" ";
                    a = a / i;
                    break;
                }
            }
        }
    }
    return 0;
}

发表于 2020-12-19 16:14:02 回复(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)
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)
#include<iostream>
#include<string>

using std::cin;using std::cout;
using std::endl;

int main()
{
    long n;
    cin>>n;
    for(int i=2;i<=n;++i)    //遍历寻找n的质因子
    {
        while(n%i==0)        //i为n的质因子
        {
            cout<<i<<" ";    //输出质因子
            n/=i;
        }
    }
    return 0;
}

发表于 2020-07-23 21:47:16 回复(0)
while True:
    try:
        n,res= int(input()),[]
        for i in range(2,n//2+1):
            while n%i==0:
                n = n / i;
                res.append(i)
        print(' '.join(map(str,res))+' ' if res else str(n)+' ')
    except:
        break
        
发表于 2020-07-20 14:45:10 回复(0)
#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)
使用递归:
public static String getResult(long ulDataInput) { 
    for (long i = 2; i < ulDataInput / 2; i++) { 
        if (ulDataInput % i == 0) {
            System.out.print(i + " ");  
            return getResult(ulDataInput / i);  }
    } 
    return ulDataInput + " "; 
}


发表于 2020-05-02 21:37:46 回复(0)
不考虑质因子的,全都是耍流氓
贴个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)
#include<stdio.h>

int main(void)
{
    long a;

    while (scanf("%ld", &a) != EOF) {
        for(int i=2; i<=a; i++){
            while(a%i == 0){
                printf("%d ", i);
                a = a/i;
            }
        }
        printf("\n");
    }


    return 0;
}


编辑于 2020-03-21 12:43:49 回复(0)
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)
import java.util.*;
public class Main{
    public static void main(String[] args){
        List<String> resultList = new ArrayList<String>();
        Scanner in = new Scanner(System.in);
        long num = in.nextLong();
        if(num > 2){
            while(num%2 ==0){
                num /= 2;
                resultList.add(String.valueOf(2));
            }
            for(int i=3;i<=num;i++){
                if(num%i == 0){
                    num = num/i;
                    resultList.add(String.valueOf(i));
                    i--;            //对i进行重复判断,处理如3*3=9这种情况
                }
            }
            String result = "";
            for(String param:resultList){
                result += param + " ";
            }
            System.out.println(result);
        } else{
            System.out.println(num);
        }
    }
}

发表于 2019-09-04 17:33:31 回复(0)
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)
最高票的是很好的思路
#include <iostream>

using namespace std;

int main() {
    long input;
    while (cin >> input) {
        if (input == 1) {
            cout << 1 << ' ';
        } 
        for (int i = 2; i <= input;) {
            if (input % i == 0) {
                input /= i;
                cout << i << ' ';
            } else {
                ++i;
            }
        }
    }
    return 0;
}


发表于 2019-08-17 09:05:24 回复(0)