0
1 10

0
7

0
import java.io.BufferedReader;
1
import java.io.BufferedWriter;
2
import java.io.IOException;
3
import java.io.InputStreamReader;
4
import java.io.OutputStreamWriter;
5
import java.util.Arrays;
6

7
/**
8
 * 백준 전체 1016 문제 알고리즘 클래스
9
 *
10
 * @author RWB
11
 * @see <a href="https://blog.itcode.dev/posts/2021/06/23/a1016">1016 풀이</a>
12
 * @since 2021.06.23 Fri 00:22:31
13
 */
14
public class Main
15
{
16
    // 최소값
17
    private static long min;
18
    
19
    // 최대값
20
    private static long max;
21
    
22
    /**
23
     * 메인 함수
24
     *
25
     * @param args: [String[]] 매개변수
26
     *
27
     * @throws IOException 데이터 입출력 예외
28
     */
29
    public static void main(String[] args) throws IOException
30
    {
31
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
32
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
33
        
34
        long[] temp = Arrays.stream(reader.readLine().split(" ")).mapToLong(Long::parseLong).toArray();
35
        
36
        min = temp[0];
37
        max = temp[1];
38
        
39
        writer.write(Integer.toString(solve()));
40
        writer.newLine();
41
        
42
        writer.close();
43
        reader.close();
44
    }
45
    
46
    /**
47
     * 알고리즘 결과 반환 함수
48
     *
49
     * @return [int] 제곱수로 나누어 떨어지지 않는 수의 갯수
50
     */
51
    private static int solve()
52
    {
53
        int size = 0;
54
        
55
        boolean[] isNotPow = eratosthenes();
56
        
57
        for (boolean item : isNotPow)
58
        {
59
            // 제곱수로 나누어 떨어지지 않는 수일 경우
60
            if (!item)
61
            {
62
                size++;
63
            }
64
        }
65
        
66
        return size;
67
    }
68
    
69
    /**
70
     * 에라토스 테네스의 체 배열 반환 함수
71
     * true: 제곱ㄴㄴ수가 아닌 수
72
     * false: 제곱ㄴㄴ수
73
     *
74
     * @return [boolean[]] 에라토스 테네스의 체 배열
75
     */
76
    private static boolean[] eratosthenes()
77
    {
78
        int length = (int) (max - min + 1);
79
        
80
        boolean[] isNotPow = new boolean[length];
81
        
82
        for (long i = 2; i * i <= max; i++)
83
        {
84
            long pow = i * i;
85
            
86
            long start = min % pow == 0 ? min / pow : (min / pow) + 1;
87
            
88
            for (long j = start; j * pow <= max; j++)
89
            {
90
                // 제곱수의 배수로 나누어 떨어지므로 제곱ㄴㄴ수가 아님
91
                isNotPow[(int) (j * pow - min)] = true;
92
            }
93
        }
94
        
95
        return isNotPow;
96
    }
97
}

0
/**
1
 * 에라토스 테네스의 체 배열 반환 함수
2
 *
3
 * true: 제곱ㄴㄴ수가 아닌 수
4
 * false: 제곱ㄴㄴ수
5
 *
6
 * @return [boolean[]] 에라토스 테네스의 체 배열
7
 */
8
private static boolean[] eratosthenes()
9
{
10
    int length = (int) (max - min + 1);
11
    
12
    boolean[] isNotPow = new boolean[length];
13
    
14
    for (long i = 2; i * i <= max; i++)
15
    {
16
        long pow = i * i;
17
        
18
        long start = min % pow == 0 ? min / pow : (min / pow) + 1;
19
        
20
        for (long j = start; j * pow <= max; j++)
21
        {
22
            // 제곱수의 배수로 나누어 떨어지므로 제곱ㄴㄴ수가 아님
23
            isNotPow[(int) (j * pow - min)] = true;
24
        }
25
    }
26
    
27
    return isNotPow;
28
}