{% embed url=“https://www.acmicpc.net/problem/4948” %}
Solution 1.
•
풀이방법
◦
에라토스테네스의 체를 그대로 이용하였다.
◦
다만 체크할 N 값들을 배열로 받아두고, 배열의 가장 마지막 번째 자리를 구해 해당 수 * 2 만큼만 isPrime 배열길이를 잡아 딱 필요한 구간까지만 에라토스테네스의 체가 이루어지도록 하였다.
public class Bj4948 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); List<Integer> inputs = new ArrayList<>(); while (sc.hasNextInt()) { int input = sc.nextInt(); if (input == 0) break; inputs.add(input); } inputs.sort(Comparator.naturalOrder()); int max = inputs.get(inputs.size()-1) * 2; boolean[] isPrime = new boolean[max+1]; //true : 소수아님, false : 소수 isPrime[0] = isPrime[1] = true; for (int i = 2; i*i <= max; i++) { if (!isPrime[i]) { for (int j = i*i; j <= max; j += i) { isPrime[j] = true; } } } StringBuilder sb = new StringBuilder(); for (int i : inputs) { int count = 0; for (int j = i+1; j <= 2*i; j++) { if (!isPrime[j]) { count++; } } sb.append(count).append("\n"); } System.out.println(sb); }}
Java
복사
Solution 2.
•
19152 kb / 248 ms
•
풀이방법
◦
역시 에라토스테네스의 체를 이용하였지만, 에라토스테네스의 체 실행 이후, 각 위치까지의 소수의 개수를 구하도록 하는 배열을 하나 더 두어, 반복문으로 계속 count 하지 않도록 하였다.
◦
시간 복잡도 면에서 훨씬 유리하다.
package practice.algorithm.math;import java.util.Scanner;public class Bj4948_2 { private static final int MAX_NUM = 123457; private static boolean[] isPrime = new boolean[MAX_NUM*2 + 1]; private static int[] primeCount = new int[MAX_NUM*2 + 1]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); getPrime(); getCount(); StringBuilder sb = new StringBuilder(); while (sc.hasNextInt()) { int n = sc.nextInt(); if (n == 0) break; sb.append(primeCount[2 * n] - primeCount[n]).append("\n"); } System.out.println(sb); } private static void getCount() { int count = 0; for (int i = 2; i < isPrime.length; i++) { if (!isPrime[i]) { count++; } primeCount[i] = count; } } private static void getPrime() { //true : 소수 아님, false: 소수임 isPrime[0] = isPrime[1] = true; for (int i = 2; i <= Math.sqrt(isPrime.length); i++) { if (!isPrime[i]) { for (int j = i*i; j < isPrime.length; j += i) { isPrime[j] = true; } } } }}
Java
복사