https://www.acmicpc.net/problem/1456
이 문제는 파이썬으로는 금방 풀었지만, 자바는 아직 미숙해서 한참 헤맸던 문제다.
그 이유는 뒤에서 다루겠다.
<문제 풀이>
1. 거의 소수를 구하기 위해 소수를 먼저 구한다.
- 소수는 B의 제곱근까지만 구해준다.
- 예를 들어 B가 10^14이고 현재 소수가 B의 제곱근인 10^7일 때, 거의 소수는 10^7에 제곱을 한 10^14가 된다.
- 그 이상의 거의 소수에 대해서는 범위를 넘어가기 때문에 구해줄 필요가 없다.
- 즉 B의 제곱근인 10^7보다 큰 소수는 거의 소수를 구해도 범위를 초과해버리기 때문에 계산에 필요하지 않다.
- 따라서 B의 제곱근까지만 소수를 구해도 B의 범위 내에 있는 거의 소수를 모두 구할 수 있다.
2. 거의 소수를 구한다.
문제 풀이 자체는 어렵지 않지만, 자료형에 대한 지식이 부족해서 많이 헤맸다.
Code(Python)
import math
import sys
input = sys.stdin.readline
def erato(): # 소수 구하기
for i in range(2, int(math.sqrt(len(sosu))) + 1):
if sosu[i]:
for j in range(i * i, len(sosu), i):
sosu[j] = False
def finalCal(): # 거의 소수 개수 구하기
cnt = 0
for i in range(2, len(sosu)): # 소수 리스트를 돌면서
if sosu[i]: # 현재 숫자(i)가 소수이면,
j = i * i # 소수 거듭제곱하기
# 거의 소수 판별
while j <= B: # 거듭제곱한 수가 B보다 작고
if A <= j: # A보다 크다면
cnt += 1 # 개수 + 1
j *= i # 현재 소수(i)를 계속 제곱하면서 진행
return cnt
A, B = map(int, input().split())
sosu = [False, False] + [True] * (int(math.sqrt(B)) - 1) # 거의 소수의 최댓값의 제곱근까지만 소수를 구하면 된다.
erato() # 소수 구하기
print(finalCal()) # 거의 소수 개수 구하기
파이썬으로는 큰 문제 없이 금방 풀었으나, 자바로 넘어오면서 많이 헤맸다.
<파이썬에서는 볼 수 없었던 오류가 자바에서 뜬 이유>
바로 정수 자료형의 허용 범위 때문이였다.
현재 자료형의 최대 범위를 넘어가는 수가 해당 변수에 들어왔다는 얘기인데, 왜 파이썬에서는 그런 오류가 안 떴을까?
<파이썬 특징>
이 분의 글을 참고했다.
Python의 int 자료형은 어떻게 범위가 무제한일까?
Question >Python의 int 자료형은 어떻게 범위가 무제한일까? 00. 개요 어떠한 프로그램이든, 정수 변수를 다룬다면 필연적으로 정수 오버플로우가 발생하기 마련인데, 파이썬은 이를 극복하고 있습니
velog.io
<3줄 요약>
파이썬2에는 이전에 int와 long의 두 가지 정수형 데이터 타입이 존재했다.
이 때 long 자료형은 무제한의 자릿수를 제공하는 정수형을 의미하는 Arbitrary precision을 지원한다.
그리고 파이썬3으로 넘어오면서 long 자료형이 int 자료형을 대체하게 되었다.
그래서 파이썬에서는 아무리 큰 수가 변수에 들어와도 오류가 뜨지 않았던 것이다.
여기까지는 이해했다.
자바에서 int 자료형은 최대 10^9승까지 담을 수 있고, long 자료형은 10^18승까지 담을 수 있다.
그래서 자바의 자료형을 long으로 바꿔서 코드를 짰다.
그러나 또 오류가 발생했다.
여기서부터는 자료형의 문제라기보다는 코드를 좀 더 신중하게 짜지 못 한 나의 잘못이 컸다.
Code(Java) - 오류 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static long A;
static long B;
static boolean[] sosu;
static int limit = 10000000;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
A = Long.parseLong(st.nextToken());
B = Long.parseLong(st.nextToken());
sosu = new boolean[limit + 1];
erato();
System.out.println(finalCal());
}
private static int finalCal() {
int cnt = 0;
for (int i = 1; i < limit + 1; i++) {
if (!sosu[i]) {
long j = i * i;
while (j < B + 1) {
if (A <= j) {
cnt += 1;
}
j *= i;
}
}
}
return cnt;
}
private static void erato() {
sosu[0] = sosu[1] = true;
for (int i = 2; i < Math.sqrt(limit) + 1; i++) {
if (!sosu[i]) {
for (int j = i * i; j < limit + 1; j += i) {
sosu[j] = true;
}
}
}
}
}
위 코드에서 오류가 발생한 지점은
private static int finalCal() {
int cnt = 0;
for (int i = 1; i < limit + 1; i++) {
if (!sosu[i]) {
long j = i * i; // 이 부분과
while (j < B + 1) {
if (A <= j) {
cnt += 1;
}
j *= i; // 이 부분이 오류 발생 원인
}
}
}
return cnt;
}
해당 함수이다.
j를 long으로 선언했다. 따라서 j에는 10^18까지 숫자가 들어갈 수 있다.
만약 i가 10^7일 경우를 생각해보자.
그럼 처음 j에는 10^14가 들어갈 것이다. 10^14가 범위 내에 존재해서 또 다시 10^7을 제곱하게 되면,
j는 10^21이 될 것이다. 그러나 이는 long형의 최대 범위를 넘어서게 된다.
그래서 이 부분에서도 long 자료형의 제한 범위를 넘지 않게 코드를 수정해야 한다.
해당 부분은 유튜브를 보고 이해했다.
https://www.youtube.com/watch?v=iDB2_JROkh8&t=783s
거듭제곱하는 수가 범위를 벗어나지 않도록 계속해서 나눗셈을 하면 된다.
즉 이항 정리를 하면 되는 것인데,
위에서 i가 10^7이라고 했을 때 범위를 벗어나게 되는 경우는 (10^7)^3이었다.
즉 (10^7)^3 <= B를 해야하는 것인데, 이렇게 되면 범위를 벗어나게 되므로,
이항정리를 이용해 양 변을 (10^7)^2로 나누어 10^7 < B / (10^7)^2를 활용하는 것이다.
Code #1(Java) - 나눗셈 활용
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Boj_1456 {
static long A;
static long B;
static boolean[] sosu;
static int limit;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
A = Long.parseLong(st.nextToken());
B = Long.parseLong(st.nextToken());
limit = (int) Math.sqrt(B); // 입력받은 B의 제곱근까지만 소수 구하기
sosu = new boolean[limit + 1]; // 소수 판별 리스트
erato(); // 소수 판별
System.out.println(finalCal());
}
private static int finalCal() {
int cnt = 0;
for (int i = 1; i < limit + 1; i++) { // 소수 판별 리스트를 돌면서
if (!sosu[i]) { // 소수이면
long curSosu = i; // 밑
int k = 1; // 지수(처음 거듭제곱은 지수가 2일 테니 1로 초기화하여 나눠준다.)
while (curSosu <= B / Math.pow(curSosu, k)) { // 이항 정리 사용
if ( A / Math.pow(curSosu, k) <= curSosu) { // 이항 정리 사용
cnt++; // 현재 거의 소수가 범위 내에 존재하면 결과값 + 1
}
k++; 지수 + 1
}
}
}
return cnt;
}
private static void erato() {
sosu[0] = sosu[1] = true;
for (int i = 2; i < Math.sqrt(limit) + 1; i++) { // 구하고자 하는 소수의 최대 범위의 제곱근까지만 계산(에라토스테네스의 체)
if (!sosu[i]) {
for (int j = i * i; j < limit + 1; j += i) {
sosu[j] = true;
}
}
}
}
}
굳이 나눗셈을 하지 않아도 풀리는 코드를 생각해냈다.
결국 long 자료형에 10^18을 넘어가는 숫자가 들어가지만 않으면 되는 것 아닌가?
코드로 보자.
Code #2(Java) - 나눗셈 활용 X
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static long A;
static long B;
static boolean[] sosu;
static int limit;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
A = Long.parseLong(st.nextToken());
B = Long.parseLong(st.nextToken());
limit = (int) Math.sqrt(B);
sosu = new boolean[limit + 1];
erato(); // 소수 판별
System.out.println(finalCal());
}
private static int finalCal() {
int cnt = 0;
for (int i = 1; i < limit + 1; i++) {
if (!sosu[i]) {
long curSosu = i;
int k = 2;
while (Math.pow(curSosu, k) <= B ) {
if (A <= Math.pow(curSosu, k)) {
cnt++;
}
k++;
}
}
}
return cnt;
}
private static void erato() {
sosu[0] = sosu[1] = true;
for (int i = 2; i < Math.sqrt(limit) + 1; i++) {
if (!sosu[i]) {
for (int j = i * i; j < limit + 1; j += i) {
sosu[j] = true;
}
}
}
}
}
위 코드처럼 굳이 나눗셈을 하지 않아도 long 자료형인 curSosu에는 10^18을 넘어가는 수가 들어가지 않기 때문에 문제를 통과할 수 있었다.
이번 기회에 자료형의 중요성을 확실히 각인시킨 것 같다.