약수의 개수가 짝수/even(약수의 개수가 짝수 알고리즘)

20151025

*이문제는 dovelet 에 있는 알고리즘 문제입니다.

약수의 개수가 짝수/even 

프로그램 명: even(open)     

프로그램 명: even(open)

제한시간: 1 초

두 정수 A, B (1 <= A <= B <= 2,000,000,000) 가 주어질때 A 와 B 사이 (A, B 포함) 에 약수의 개수가 짝수인 수의 개수를 출력하시오.

입력

두 정수 A, B 가 주어진다.

출력

약수의 개수가 짝수인 수의 개수를 출력하시오.

입출력 예

입력

3 17

출력 

12

출처:likepad

문제 풀이

1) 풀이

import java.io.PrintStream;
import java.util.Scanner;

public class Main {
 
	Scanner sc = new Scanner(System.in);
	static PrintStream p = System.out;
	int a, b;
	
	public static void main(String[] args) {
		Main m = new Main();
		m.input();
		m.Output();
	}
	void input(){
		a = sc.nextInt();
		b = sc.nextInt();
	}
	void Output(){
		int bb = b-(int)(Math.sqrt(b));
		System.out.println((int)(Math.sqrt(b)));
		int aa = (a-1)-(int)(Math.sqrt(a-1));
		p.println(bb-aa);
	}  
}

void Output(){   //처음 문제를 풀때 짝수인 약수를 구별하기 위해서 이런식으로 코딩했었죠. 그냥 참고용 입니다.ㅎ 
	int realSum = 0;
	for(int ta =a; ta <= b; ta++){   // a b 사이 값 하나씩
		int sum = 0;
		for(int taa = 1; taa <= ta; taa++){     // 값 a개 1개를 가져옴
			if(ta%taa == 0){              //a의 소수점 개수를 찾음
				System.out.println(taa);
				sum = sum + 1;
			}
		}
		if(sum%2 == 0){
			realSum = realSum + 1;
		}
	}
	p.println(realSum);
}

*짧게 코딩하는것도 좋지만 저는 함수와 객체 지향개념을 쓰고 싶어서 이렇게 코딩 했습니다.

처음에 for 문으로 풀었더니 시간초과로 틀렸습니다. 식으로 풀게 하는 문제고 흰트가 나와 있는데

루트 값을 정수로 어느시점에 변환 해야 하는지, 소수점 반올림 처리를 해서 정수로 만들어야 하는지

이런 부분에서 오랜시간 고생했던 문제입니다.  

아래 흰트 개념이 있습니다. 

흰트 개념을 보시면 수식은 어렵지 않아요.

흰트 개념에서 설명이 1 부터 n 까지 짝수개인 약수 값이 나오는걸 알려줬지만 우린 a 부터 b 까지의

범위를 알기를 원합니다. 그래서 1부터  b 까지 구한 값에 1부터 a-1 까지(a보다 -1 작은수)구한 값을 빼주기만 하면 됩니다.

흰트 개념

반복문을 사용하면  시간 초과가 납니다.  식으로  답을 구해야 합니다.

---

1 에서 n 사이 중 약수의 개수가 짝수인 수의 개수를 구하는 문제.

약수의 개수가 홀수인 수는 제곱수. 

1 에서 n 사이 중 제곱수의 개수는    개 이므로 

예를 들어 ,   1 ~ 17 사이 약수의 개수가 짝수인 수는