[Cos Pro 1급 java] [4차] 문제10) 소수의 세제곱이 몇개가 있나요 - 에라스토테네스의 체 사용

안녕하세요

 

이번 포스팅은 Cos Pro 1급 java  4차 기출문제 중 10번 문제인 소수의 세제곱이 몇개가 있나요 문제를 풀어보겠습니다.

 

백준 온라인 저지에서도 한번 다뤄봤던 내용이라 링크를 걸어두도록 하겠습니다.

 

drcode-devblog.tistory.com/64?category=934211

[백준/java] 1929 소수 구하기 - 에라스토테네스의 체 사용

□ 문제설명

자연수를 제곱한 수는 제곱수, 세 제곱한 수는 세제곱 수라고 합니다. 예를 들어 2^2 = 4 는 제곱수, 3^3 = 27은 세제곱수 입니다.

두 자연수 a, b가 주어질 때 a 이상 b 이하인 자연수 중 소수의 제곱수와 세제곱수의 개수를 구하려 합니다. 예를 들어 a = 6, b = 30일 때 소수의 제곱수는 [9, 25]로 2개, 소수의 세제곱수는 [8, 27]로 2개로 총 4개입니다.

두 자연수 a, b가 매개변수로 주어질 때, a 이상 b 이하인 제곱수와 세제곱수의 개수의 합을 return 하도록 solution 함수를 완성해주세요.

---

□ 매개변수 설명

두 자연수 a, b가 solution 함수의 매개변수로 주어집니다.

• a, b는 각각 1 이상 1,000,000,000 이하인 자연수입니다.
• a ≤ b인 경우만 입력으로 주어집니다.

---

□ return 값 설명

 a 이상 b 이하인 제곱수와 세제곱수의 개수의 합을 return 해주세요.

---

□ 예시

a	b	return
6	30	4

---

□ 예시설명

6 이상 30 이하인 수중 소수의 제곱수는 다음과 같습니다.

• 3^2 = 9
• 5^2 = 25

소수의 세제곱 수는 다음과 같습니다.

• 2^3 = 8
• 3^3 = 27

따라서 4를 return 하면 됩니다.

 

※ 문제 접근 방법

(1)  Boolean ArrayList를 만듭니다

(2) 리스트의 인덱스를 0부터 b까지 채워줍니다.(0, 1 : false, 2 이상 true

(3) i를 제곱한 수가 b보다 작을 때 for문을 순회합니다.

(4) 제곱 수의 인덱스일 때, 해당 인덱스들은 모두 false로 바꿔줍니다.

 

import java.util.*;

class Main {
    public int solution(int a, int b) {
        int answer = 0;
		
	List<Boolean> list = new ArrayList<Boolean>();
	list.add(false); list.add(false);
	for (int i = 2; i <= b; i++) list.add(true);

	for (int i = 2; i*i <= b; i++) {
		if(list.get(i)) {
			for (int j = i*i; j <= b; j += i) {
				list.set(j, false);
			}
		}
	}

	List<Integer> primeList = new ArrayList<Integer>();
	for (int i = 0; i < list.size(); i++) {
		if(list.get(i)) primeList.add(i);
	}
    
	for (int i = 0; i < primeList.size(); i++) {
		if(Math.pow(primeList.get(i), 2) <= b && Math.pow(primeList.get(i), 2) >= a) answer++;
		if(Math.pow(primeList.get(i), 3) <= b) answer++;
	}

	return answer;
   }

    // 아래는 테스트케이스 출력을 해보기 위한 main 메소드입니다.
    public static void main(String[] args){
        Main sol = new Main();
        int a = 6;
        int b = 30;
        int ret = sol.solution(a, b);

        // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
        System.out.println("solution 메소드의 반환 값은 " + ret + " 입니다.");
    }
}