백준 #4948 java 2023.01.26

문제 이름이 되게 있어보인다. 베르트랑 공준.ㅎㅎ 지금까지 소수문제를 많이 풀어봤기에 이것도 비슷하겠거니 하고 코드를 작성했다.

 

package boj_basic.step8;

import java.util.Scanner;

public class Q4948 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		while(true) {
			int sum = 0;
			int n = sc.nextInt();
			int[] arr = new int[2*n+1];
			if(n==0)
				break;
			else {
				for(int i = n+1; i<=2*n; i++) {
					if(n==1)
						arr[n]=1;
					else {
						for(int j = 2; j<i; j++) {
							if(i%j==0)
								arr[i]=1;
						}
					}
				}
			}
			for(int i = n+1; i<=2*n; i++) {
				if(arr[i]==0)
					sum+=1;
			}
			System.out.println(sum);
		}

	}

}

처음 작성한 코드는 이러했는데, 시간초과가 나왔다. 역시 전에 풀었던 에라토스테네스의 체를 이용하여 풀어야 하는 문제였다.

package boj_basic.step8;

import java.util.Scanner;

public class Q4948_1 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		while(true) {
			int sum = 0;
			int n = sc.nextInt();
			int[] arr = new int[2*n+1];
			if(n==0)
				break;
			else {
				arr[1]=1;
				for(int num = 2; num<=2*n; num++) {
					if((int)Math.pow(num, 2)>2*n) 
						break;
					else {
						for(int i =(int)Math.pow(num, 2); i<=2*n; i+=num) {
							arr[i]=1;
						}
					}
				}
			}
			for(int i = n+1; i<=2*n; i++) {
				if(arr[i]==0)
					sum+=1;
			}
			System.out.println(sum);
		}

	}

}

바뀐 코드는 이러하다. 평범한 에라토스테네스의 체 문제에서 더해진 부분은 0을 입력하면 더 이상 입력할 수 없도록 해야하는 것. 따라서 무한반복문을 만들고 n==0일 때 break;로 반복문을 빠져나올 수 있도록 작성했다.

에라토스테네스의 체 문제를 복습할 수 있었던 좋은 문제였다!