首页 > 试题广场 >

质数因子

[编程题]质数因子
  • 热度指数:1086752 时间限制: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)
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 提示用户输入一个正整数
        System.out.print("请输入一个正整数: ");
        long num = scanner.nextLong();
        
        // 只有当输入的数字大于1时才进行处理,因为1没有质因数
        if (num > 1) {
            // 找到并打印所有能够整除num的2,然后将num除以2
            while (num % 2 == 0) {
                System.out.print(2 + " ");
                num /= 2;
            }
            
            // 此时,num必须是奇数。从3开始,我们可以检查奇数因子。
            for (long i = 3; i <= Math.sqrt(num); i += 2) {
                // 当i可以整除num时,打印i并除以i
                while (num % i == 0) {
                    System.out.print(i + " ");
                    num /= i;
                }
            }
            
            // 如果在循环结束后,num是一个大于2的质数,则直接打印出来
            if (num > 2) {
                System.out.print(num);
            }
        } else {
            // 如果输入的数不大于1,则提示用户
            System.out.println("输入的数必须大于1。");
        }
       
    }
}

编辑于 2024-03-10 16:53:04 回复(0)
import java.util.ArrayList;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        long number = in.nextInt();

        long target = number;
        ArrayList<Integer> zhishu = new ArrayList<>();

        for(int a = 2; a <= number; a++) {
            int count = 0;
            for(int b = 2; b <= a; b++) {
                if(a % b == 0 && a / b != 1){
                    count++;
                    break;
                }
            }
            if(count == 0 && target % a == 0) {
                target = target / a;
                System.out.print(a + " ");
                a = 1;
            }
            if(a > Math.sqrt(target)) {
                System.out.print(target);
                break;
            }
        }
       
        in.close();
    }
}
编辑于 2024-02-28 02:03:32 回复(0)
import java.util.*;

// 普通循环判断2000000014性能总不能通过,根据正常质因子不会大于根号原数,这样貌似可以
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();

        List<Integer> resList = new ArrayList<>();
        List<Integer> otherList = new ArrayList<>();
        List<Integer> resOtherList = new ArrayList<>();
        for (int i=2; i<=Math.sqrt(num); i++) {
            while (num%i==0) {
                resList.add(i);
                otherList.add(num/i);
                num=num/i;
            }
        }
        for (Integer otherNum : otherList) {
            boolean isNeedNum = true;
            for (Integer res : resList) {
                if (otherNum%res==0 || otherNum<2) {
                    isNeedNum = false;
                    break;
                }
            }
            if (isNeedNum) resOtherList.add(otherNum);
        }
        resList.addAll(resOtherList);
        if (resList.size()==0){
            resList.add(num);
        }

        for (int i=0; i<resList.size(); i++) {
            System.out.print(resList.get(i));
            if (i!=resList.size()-1) System.out.print(" ");
        }
    }
}
发表于 2024-01-26 20:24:53 回复(0)
短除法+判断新数字是否为质数,用例100%过
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long longNum = in.nextLong();
        int i = 2;
        // 注意 hasNext 和 hasNextLine 的区别
        while (i <= longNum) { // 注意 while 处理多个 case
            if (longNum % i == 0) {
                System.out.print(i + " ");
                if (longNum == i) {
                    return;
                }
                longNum = longNum / i;
                // 判断新longNum是否是素数
                boolean flag = true;
                // 每一个整数都可以看做由两个数相乘得到,且每个乘数不大于原整数的平方根
                for (int j = 2; j <= Math.sqrt(longNum); ++j) {
                    if (longNum % j == 0) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    System.out.print(longNum);
                    return;
                }
                i = 2;
            } else {
                i++;
            }
        }
    }
}

发表于 2024-01-24 13:02:22 回复(0)
public class Main {
    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        Long l = scan.nextLong();
        String s = "";
        if (l >= 2) {
            for (int i = 2; i <= l; i++) {
                while (l % i == 0) {
                    s = s + i + " ";
                    l /= i;
                }
            }
        } else {
            System.out.println(l + s);
        }
        System.out.println(s);
    }
}
编辑于 2024-01-23 16:55:23 回复(2)
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
      	while(n % 2 == 0){
            System.out.print(2+" ");
			n/=2;
        }
		for(int i =3;i<=Math.sqrt(n);i+=2){
            while(n%i==0){
			System.out.print(i+" ");
            n/=i;
            }
        }
        if(n>2){
            System.out.print(n);
        }
}
}

编辑于 2024-01-08 18:20:34 回复(0)
public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        long num = in.nextLong();
        while (num % 2 == 0) {
            System.out.print(2 + " ");
            num = num / 2;
        }

        for (int i = 3; i <= Math.sqrt(num); i += 2) {
            while (num % i == 0) {
                System.out.print(i + " " );
                num = num / i;
            }
        }
        if (num > 2) {
            System.out.print(num + " ");
        }
    }

编辑于 2023-12-25 15:18:43 回复(0)
方法:循环除以最小质因子直到本身为质数,例如
180=2*90
90=2*45
45=3*15
15=3*5
5为质数,结束循环,得到2,2,3,3,5

实现:定义一个可变容量的有序质数表类,扩展质数表到

复杂度分析:
    为输入值;为不大于的质数的个数
    时间复杂度:O(N)
    空间复杂度:O(N)

import java.util.*;

public class Main {
    static PrimeTable primeTable = new PrimeTable();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        if (!scanner.hasNextInt()) return;
        int x = scanner.nextInt();
        primeTable.updateTo(Math.sqrt(x));
        while (x >= 2) {
            int factor = getMinPrimeFactor(x);
            System.out.printf("%d ", factor);
            if (factor == x) return;
            x /= factor;
        }
    }

    public static int getMinPrimeFactor(int x) {
        if (primeTable.isPrime(x)) return x;
        for (int n : primeTable.table) {
            if (x % n == 0) return n;
        }
        return x;
    }
}

class PrimeTable {
    List<Integer> table = new ArrayList<>();
    int last;

    public PrimeTable() {
        Collections.addAll(table, 2, 3, 5, 7, 11, 13, 17, 19); // *预设值中必须有2
        last = table.get(table.size() - 1);
    }
    // 增加追加一个质数
    public void update() {
        int candidate = last;
        while (!isPrime((candidate += 2))) {
        }
        last = candidate;
        table.add(last);
    }
    // 追加多个质数到不超过bound
    public void updateTo(double bound) {
        while (last < bound) update();
    }

    public boolean isPrime(int x) {
        if (x < 2) return false;
        if (x <= last) return table.contains(x);
        final int sqrt = (int) Math.sqrt(x);
        if (last >= sqrt) {
            for (int n : table) if (x % n == 0) return false;
            return true;
        }
        for (int i = last + 2; i <= sqrt; i += 2) {
            if (x % i == 0) return true;
        }
        return false;
    }
}


发表于 2023-10-29 15:08:37 回复(0)
判断x是不是质数时,尝试到x^1/2即可
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int x=in.nextInt();
        if(x==1){
            return;
        }
        int p=2;
        while(!isPrime(x)){
            while(x%p!=0){
                p=nextPrime(p);
            }
            System.out.print(p+" ");
            x/=p;
        }
        System.out.print(x);
    }

    private static int nextPrime(int curr){
        if(curr==2){
            curr++;
        }else{
            curr+=2;
        }
        while(!isPrime(curr)){
            curr+=2;
        }
        return curr;
    }
    private static boolean isPrime(int x){
        for(int i=2;i*i<=x;i++){
            if(x%i==0){
                return false;
            }
        }
        return true;
    }
}


发表于 2023-09-10 14:14:44 回复(0)
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int target = in.nextInt();
            int y = 2;
            while (target != 1) {
                if (target % y == 0) {
                    System.out.print(y + " ");
                    target /= y;
                } else {
                    if (y > target / y) y = target;
                    else y++;
                }
            }
        }
    }
}
发表于 2023-08-24 15:20:31 回复(1)
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            while (a % 2 == 0) {
                System.out.print(2 + " ");
                a /= 2;
            }
            for (int i = 3; i * i <= a; i += 2) {
                while (a % i == 0) { //prime factor
                    System.out.print(i + " ");
                    a /= i;
                }
            }
            if (a > 2) {
                System.out.println(a);
            }
        }
    }
}
发表于 2023-08-20 00:28:16 回复(0)
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// System.out.print("请输入一个正整数:");
long number = scanner.nextLong();

List<Long> primeFactors = new ArrayList<>();
// 检查小于等于 √number 的质数作为可能的质因子
for (long i = 2; i * i <= number; i++) {
while (number % i == 0) {
primeFactors.add(i);
number /= i;
}
}

// 如果 number 大于 1,说明它本身就是一个质因子
if (number > 1) {
primeFactors.add(number);
}
primeFactors.forEach(factor-> System.out.print(factor + " "));

}
}
发表于 2023-08-16 16:41:33 回复(0)
    public static void judge (int a){
        for(int i = 2 ; i <= Math.sqrt(a);){
            if(a % i == 0){
            a /= i;
            System.out.print(i + " ");
            continue;
            }
            i++ ;
        }
        if(a != 1){
            System.out.print(a);
        }
    }
发表于 2023-08-15 16:33:34 回复(0)
public static void main(String[] args) {
        int a=90;
        int b=2;
        while (b<a){
            if (a%b==0){
                System.out.println(b);
                a=a/b;
            }else {
                b++;
            }
        }
        System.out.println(b);
    }

发表于 2023-08-07 16:41:10 回复(0)
import java.util.*;
import java.lang.Math;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLong()) { // 注意 while 处理多个 case
        //考虑排序 
            // long a = in.nextLong();
            // List<Long> list=new ArrayList();

            // Long b=2l;

            // while(b<(Math.sqrt(a)+1)){
            //     if(a%b==0){
            //         list.add(b);
            //         a=a/b;
            //     }else{
            //         b++;
            //     }
            // }

            // list.add(a);

            // Collections.sort(list);

            // for(long i:list){
            //     System.out.print(i+" ");
            // }

        // 不考虑排序,本身就会是有序的
            long a = in.nextLong();

            Long b=2l;

            while(b<(Math.sqrt(a)+1)){
                if(a%b==0){
                    System.out.print(b+" ");
                    a=a/b;
                }else{
                    b++;
                }
            }

             System.out.print(a);
            
        }
    }
}

发表于 2023-08-05 22:06:06 回复(0)
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
         Scanner scanner = new Scanner(System.in);
        long next = scanner.nextLong();
        //最大循环为平方后的数值
        long num = (long) Math.sqrt(next);
        //判断本身是不是质数
        int flag=0;
        //循环输出质数因子
        for (int i = 2; i <= num; i++) {
            while (next % i == 0) {
                System.out.print(i + " ");
                flag++;
                next /= i;
            }
        }
        //大于平方根的质数因子最多只能有一个,那就是原数除以最后的质数因子,需要排除掉本身就是质数的例子
        if(next > num && flag > 0){
            System.out.println(next + " ");
        }
        //本身是质数,输出自己
        if (flag == 0) {
            System.out.println(next + " ");
        }
    }
}

发表于 2023-07-17 18:46:29 回复(0)
递归yyds

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        yin(num);
    }

    public static int yin(int num) {
        int sq_num = (int)Math.sqrt(num);
        for (int i = 2 ; i <= sq_num ; i++) {
            if (num % i == 0) {
                System.out.print(i+" ");
                return yin(num/i);
            }
        }
        System.out.print(num);
        return num;
    }


}


发表于 2023-06-19 15:46:13 回复(0)