SWEA 10965. 제곱수 만들기

어떤 자연수 A가 주어진다. 여기에 자연수 B를 곱한 결과가 거듭제곱수가 되는 최소의 B를 구하는 문제이다.

 

거듭제곱수는 소수인 약수가 짝수갯수 만큼 곱해진 형태이다. 주어진 수를 소인수분해해야 하므로 먼저 주어진 A의 범위 내의 모든 소수를 찾는다. 이후, 순서대로 순회하면서 나누어떨어질 경우 안 나누어질 때 까지 나누었을 때 나눈 횟수가 짝수가 아니면 해당 수를 한 번 더 곱해주어야 한다. 이를 계속 누적곱해준 수가 최소 B가 된다.

boolean[] isPrime = new boolean[maxSqrt + 1];
for (int i = 2; i <= maxSqrt; i++) {
    isPrime[i] = true;
}
        
for (int i = 2; i * i <= maxSqrt; i++) {
    if (isPrime[i]) {
        for (int j = i * i; j <= maxSqrt; j += i) {
            isPrime[j] = false;
        }
    }
}
        
ArrayList<Integer> primes = new ArrayList<>();
for (int i = 2; i <= maxSqrt; i++) {
    if (isPrime[i]) {
        primes.add(i);
    }
}

int A = Integer.parseInt(br.readLine().trim());
int ans = 1; 
            
for (int p : primes) {
    if (p * p > A) break;
                
    int count = 0;
    while (A % p == 0) {
        A /= p;
        count++;
    }
                
    if (count % 2 != 0) {
        ans *= p;
    }
}
if (A > 1) {
    ans *= A;
}
sb.append(ans).append("\n");

 

 

결과 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Solution {
    public static void main(String[] args) throws IOException {
        int maxA = 10000000;
        int maxSqrt = (int) Math.sqrt(maxA);
        boolean[] isPrime = new boolean[maxSqrt + 1];
        for (int i = 2; i <= maxSqrt; i++) {
            isPrime[i] = true;
        }
        
        for (int i = 2; i * i <= maxSqrt; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= maxSqrt; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        ArrayList<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= maxSqrt; i++) {
            if (isPrime[i]) {
                primes.add(i);
            }
        }
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        
        StringBuilder sb = new StringBuilder();
        for (int tc = 1; tc <= T; tc++) {
            sb.append('#').append(tc).append(' ');
            int A = Integer.parseInt(br.readLine().trim());
            int ans = 1; 
            
            for (int p : primes) {
                if (p * p > A) break;
                
                int count = 0;
                while (A % p == 0) {
                    A /= p;
                    count++;
                }
                
                if (count % 2 != 0) {
                    ans *= p;
                }
            }
            if (A > 1) {
                ans *= A;
            }
            sb.append(ans).append("\n");
             
        }
        
        br.close();
        System.out.print(sb);
    }
}