BOJ 1016 제곱 ㄴㄴ 수

제곱ㄴㄴ수를 판별하기 위한 Set을 하나 생성한다.
일반적으로는 배열을 이용하지만 본 풀이에서는 중복 제거와 적은 메모리 사용을 위해 Set을 이용하였다.
2부터 $\sqrt{max}$ 까지 제곱하며 그의 배수를 모두 Set에 저장한다.
예를 들어 $2^2 \times 1, 2^2 \times 2, 2^2 \times 3 ... 2^2 \times K$ 의 수들은 모두 제곱수의 배수이므로 Set에 저장한다. 이때 $2^2 \times K \leq max$ 인 만큼만 반복한다.
Set에 저장되어 있는 숫자들은 모두 제곱ㄴㄴ수가 아닌 숫자이므로, 전체 숫자의 개수(max - min + 1)에서 Set의 크기를 뺀 값이 제곱ㄴㄴ수의 개수이다.

코드 보기(Java)

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        HashSet<Long> set = new HashSet<>();

        // 시작과 끝 입력
        String[] str = br.readLine().split(" ");
        long min = Long.parseLong(str[0]);
        long max = Long.parseLong(str[1]);

        // 에라토스테네스의 체
        int end = (int)Math.sqrt(max);
        for(long i = 2; i <= end; i++) {
            long square = i * i;
            long start = min / square; // 시작점 계산
            if(min % square != 0) start++; // 시작점 보정

            // set에 제곱수 넣기
            for(long j = start; j * square <= max; j++) {
                set.add(j * square);
            }
        }

        // 전체 개수에서 제곱의 개수 빼기
        System.out.println(max - min + 1 - set.size());
    }
}

코드 보기(C++)

#include <iostream>
#include <cmath>
#include <set>

#define fastio ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
#define endl '\n'

using namespace std;

int main() {
    fastio;
    
    set<long> s;
    
    // 시작과 끝 입력
    long min, max;
    cin >> min >> max;

    // 에라토스테네스의 체
    int end = (int)sqrt(max);
    for(long i = 2; i <= end; i++) {
        long square = i * i;
        long start = min / square; // 시작점 계산
        if(min % square != 0) start++; // 시작점 보정

        // set에 제곱수 넣기
        for(long j = start; j * square <= max; j++) {
            s.insert(j * square);
        }
    }

    // 전체 개수에서 제곱의 개수 빼기
    cout << (max - min + 1 - s.size()) << endl;
    
    return 0;
}

코드 보기(Kotlin)

import kotlin.math.sqrt

fun main(args: Array<String>) = with(System.`in`.bufferedReader()) {
    var set: MutableSet<Long> = mutableSetOf()

    // 시작과 끝 입력
    var str = readLine().split(" ")
    var min = str[0].toLong()
    var max = str[1].toLong()

    // 에라토스테네스의 체
    var end = sqrt(max.toDouble()).toInt()
    for(i in 2..end) {
        var square = i * i
        var start = min / square // 시작점 계산
        if(min % square != 0L) start++ // 시작점 보정

        // set에 제곱수 넣기
        for(j in start..(max / square)) {
            set.add(j * square)
        }
    }

    // 전체 개수에서 제곱의 개수 빼기
    println(max - min + 1 - set.size)
}

코드 보기(Python)

from sys import stdin
import math

def main():
    s = set()

    # 시작과 끝 입력
    str = stdin.readline().split(" ")
    min = int(str[0])
    max = int(str[1])

    # 에라토스테네스의 체
    end = int(math.sqrt(max))
    for i in range(2, end + 1):
        square = i * i
        start = min // square # 시작점 계산
        if min % square != 0:
            start = start + 1 # 시작점 보정

        # set에 제곱수 넣기
        for j in range(start, (max // square) + 1):
            s.add(j * square)

    # 전체 개수에서 제곱의 개수 빼기
    print(max - min + 1 - len(s))

if __name__ == "__main__":
    main()

코드 보기(Swift)

import Foundation

func main() {
    var set =  Set<Int64>()

    // 시작과 끝 입력
    var str = readLine()!.split(separator: " ")
    var min = Int64(str[0])!
    var max = Int64(str[1])!

    // 에라토스테네스의 체
    var end = Int(sqrt(Double(max)))
    for i in 2..<end + 1 {
        var square = Int64(i) * Int64(i)
        var start = min / square // 시작점 계산
        if(min % square != 0) { // 시작점 보정
            start += 1
        }

        // set에 제곱수 넣기
        for j in start..<(max / square) + 1 {
            set.insert(j * square)
        }
    }

    // 전체 개수에서 제곱의 개수 빼기
    print(max - min + 1 - Int64(set.count))
}

main()