fork download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.math.*;
  4. import java.io.*;
  5.  
  6. import static java.lang.Math.*;
  7. import static java.util.Arrays.*;
  8.  
  9. public class CompositeSmash {
  10.  
  11. 	int INF=1<<28;
  12. 	double EPS=1e-9;
  13.  
  14. 	int n,target;
  15. 	int[] flag;
  16.  
  17. 	public String thePossible(int n, int target) {
  18. 		this.n=n;
  19. 		this.target=target;
  20. 		flag=new int[n+1];
  21. 		fill(flag,-1);
  22. 		return rec(n)==1?"Yes":"No";
  23. 	}
  24.  
  25. 	int rec(int m){
  26. 		if(flag[m]>=0){
  27. 			return flag[m];
  28. 		}
  29.  
  30. 		if(m==target){
  31. 			return flag[m]=1;
  32. 		}
  33.  
  34. 		int res=1;
  35. 		boolean prime=true;
  36. 		for(int i=2;i*i<=m;i++){
  37. 			if(m%i==0){
  38. 				if(rec(i)==1||rec(m/i)==1){
  39. 					prime=false;
  40. 				}else{
  41. 					res=0;
  42. 					break;
  43. 				}
  44. 			}
  45. 		}
  46. 		if(prime){
  47. 			res=0;
  48. 		}
  49. 		return flag[m]=res;
  50. 	}
  51.  
  52. 	void debug(Object...os){
  53. 		System.err.println(Arrays.deepToString(os));
  54. 	}
  55.  
  56. }
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/5vhMP
language:
Java (HotSpot 12)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!