백준_1456 거의 소수 (에라토스테네스의 채)Algorithm/Algorithm 문제2024. 2. 2. 12:53
Table of Contents
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BJ_1456_거의소수 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
long a = Long.parseLong(st.nextToken());
long b = Long.parseLong(st.nextToken());
long[] arr = new long[10000001];
int i, j;
for(i=2; i<arr.length; i++) {
arr[i] = i;
}
for (i=2; i<=Math.sqrt(arr.length); i++) {
if (arr[i] == 0) {
continue;
}
for (j=i*2; j<arr.length; j+=i) {
arr[j] = 0;
}
}
long temp;
int result = 0;
for (i=2; i<arr.length; i++) {
if (arr[i] == 0) {
continue;
}
temp = arr[i];
while((double)arr[i] <= (double)b/(double)temp) { //이항하지 않으면 long범위 넘어버릴수도 있음
if((double)arr[i] >= (double)a/(double)temp){
result++;
}
temp *= arr[i];
}
}
System.out.println(new StringBuilder().append(result));
}
}
'Algorithm > Algorithm 문제' 카테고리의 다른 글
백준_1016 제곱ㄴㄴ수 (에라토스테네스의 채) (0) | 2024.02.04 |
---|---|
백준_1747 소수&팰린드롬 (에라토스테네스의 채) (0) | 2024.02.03 |
백준_1929 소수 구하기 (에라토스테네스의 채) (1) | 2024.02.01 |
백준_1541 잃어버린 괄호 (그리디) (0) | 2024.01.31 |
백준_1931 회의실 배정 (그리디) (0) | 2024.01.30 |
@kjyyjk :: 녕의 학습 기록
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!