[Codewar] Sections

https://www.codewars.com/kata/sections/train/java

Codewars: Train your coding skills

Consider the following equation of a surface S: z*z*z = x*x * y*y.
Take a cross section of S by a plane P: z = k where k is a positive integer (k > 0).
Call this cross section C(k).

Task

Find the number of points of C(k) whose coordinates are positive integers.

Examples

If we call c(k) the function which returns this number we have

c(1) -> 1 c(4) -> 4 c(4096576) -> 160 c(2019) -> 0 which means that no point of C(2019) has integer coordinates.

 

 

 

 

 idea는 k의 제곱근을 A 라 하면 A^3의 약수의 수가 결과값임

 

Solution(fail)

class Section {
    
    public static int c(long k) {
		
		int count=0;
		long z = k;
		long x = (long) Math.sqrt(z);
		if(x*x == z) {
			//long n = x*x*x;
			long n = (long) Math.pow(x, 3);
			for(long i =1; i*i<n; i++)
			{
				if(n%i==0) {count ++;}
				else if(i*i==n) {count ++;}
			}
	  return count;
	}
}

 

큰 수 일경우 시간이 오래걸림

 

-> 검사 수를 대폭 감소를 해봄

: idea는 간단함 1~100의 약수를 구하면 1, 2, 4, 5, 10, 20, 25, 50 ,100 인데 검사 수를 10 까지만 하는거임

: 어차피 10까지만 검사해서 나머지가 0이면 2배를 이용하면 구할 수 있음

 

Solution(fail2)

class Section {
    
    public static int c(long k) {
    
	int count=0;
	long z = k;
	if(z==1){return 1;}
      
	long x = (long) Math.sqrt(z);
	if(x*x == z) {
		long n = (long) Math.pow(x, 3);
		long ren = (long) Math.sqrt(n);

         
		for(long i=1; i<=ren; i++){ 
			if(n%i==0){count++;}
		}
	}
	else return 0;
	//System.out.println(count);
      
	return count*2;
	}
}

 

이렇게 코드를 짰을 때 시간이 대폭 감소했음 

그러나 제출했을때는 시간 초과로 실패함

 

그래서 찾아본 결과 약수의 수를 구하는 공식이 있었음

 

약수의 수 구하는 공식

즉  A^3를 소인수 분해 하여서 지수를 구해야 함

 

 

Solution

class Section {
    
	public static int c(long k) {
    
 		int count=1;
		long z = k;
		if(z==1){return 1;}
      
		long x = (long) Math.sqrt(z);
		if(x*x == z) {
			long n = (long) Math.pow(x, 3);
			for(long i=2; i<=n; i++){ 
				int e = 0;
				for(; n%i==0; e++){n/=i;}
				count*= e+1;
			}
		}
		else return 0;

		return count;
	}
}

count를 약수의 수, e는 지수

 

소인수 분해를 해서(for 반복문을 이용해서 구함) 구하였음