HDU 1164-Eddy's research I

我不是女神ヾ 2022-05-15 01:11 129阅读 0赞

*  ## HDU 1164-Eddy's research I ##

--------------------

*  ## 题目链接：[Eddy's research I][Eddy_s research I] ##
 *  ## 思路： ##

### 题目大意： ###

把一个数分解乘素数相乘的运算式

### 坑： ###

素数在运算式中是升序排列的，这个通过重复检测同个因数可以解决

### 说句话： ###

本来这道题简单到我不想发，可我真的WA了很多遍，也是今天才尝试用java写，对java不熟悉的缘故

用了 hasNextLine() 控制多输入，其实没有必要，一行就一个数，***用 hasNextInt() 足够***

哭死

*  ## 代码： ##

import java.util.Arrays;
    import java.util.Scanner;
    public class Main {
    
    	private static final int MAX_SIZE = 70000;
    	static boolean[] Era=new boolean[MAX_SIZE];
    	static int[] Prime=new int[MAX_SIZE];
    	static int Depth=0;
    	static int Num;
    	static int[] Res=new int[MAX_SIZE];
    	public static void Eratosthenes() {
    		Arrays.fill(Era, true);
    		for(int i=2;i*2<=MAX_SIZE;i++) {   //筛素数
    			if(Era[i]) {
    				for(int j=2*i;j<MAX_SIZE;j+=i)
    					Era[j]=false;
    			}
    		}
    		Prime[0]=2;
    		int j=0;
    		for(int i=3;i<MAX_SIZE;i++) {    //存素数
    			if(Era[i]) {
    				Prime[++j]=i;
    			}
    		}
    	}
    	
    	public static void Solve() {
    		int i=0;
    		while(Num>1) {
    			while(Num%Prime[i]==0) {
    				Num/=Prime[i];
    				Res[++Depth]=Prime[i];
    			}
    			i++;
    		}
    	}
    	public static void main(String[] args) {
    		// TODO 自动生成的方法存根
    		Scanner in=new Scanner(System.in);
    		Eratosthenes();
    		while(in.hasNextInt()) {     //不能hasNextLine()
    			Num=in.nextInt();
    			Depth=0;
    			if(Num==1) {
    				System.out.println("1");  
    				continue;
    			}
    			Solve();
    			for(int i=1;i<=Depth;i++) {
    				System.out.print(Res[i]);
    				if(i!=Depth) {
    					System.out.print("*");
    				}
    			}
    			System.out.println();
    		}
    	}
    }

[Eddy_s research I]: http://acm.hdu.edu.cn/showproblem.php?pid=1164