[백준]1016. 제곱 ㄴㄴ수 (java, python)

링크

제곱 ㄴㄴ수

문제 분석

• min과 max값이 크지만 범위 자체는 100만이기 때문에 배열로 저장 가능합니다
• 에라토스테네스의 체와 비슷한 원리로 2부터 sqrt(max)까지 반복하며 제곱수들로 나누어지는지 확인합니다
• 인덱스 처리를 꼼꼼히 해줍니다

코드

JAVA

import java.util.*;

public class Q1016 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long min = sc.nextLong();
        long max = sc.nextLong();
        long count = max - min + 1;
        boolean[] chk = new boolean[(int)count];
        int n = 2;
        while(Math.pow(n, 2) <= max) {
            long square = (long)Math.pow(n, 2);
            long i = min / square;

            while(square * i <= max) {
                long idx = square * i - min;
                if(idx >= 0 && !chk[(int)idx]) {
                    count--;
                    chk[(int)idx] = true;
                }
                i++;
            }
            n++;
        }
        System.out.println(count);
    }
}

PYTHON

min, max = map(int, input().split())

chk = [1] * (max - min + 1)
for n in range(2, int(max ** 0.5) + 1):
    square = n ** 2
    i = min // square
    if square * i < min:
        i += 1
    while square * i <= max:
        chk[square * i - min] = 0
        i += 1
print(sum(chk))