[백준 1929] 소수 구하기 JAVA

---

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int start = 0, end = 0;
        int cnt = 0;
        start = sc.nextInt();
        end = sc.nextInt();

        //소수는 약수를 1과 자기 자신만 가짐
		for (int i = start; i <= end; i++) { // 처음 수부터 끝 수까지 돈다.
			switch (i) {
			case 1: {
				continue;
			}
			case 2: {
				System.out.println(i);
				continue;
			}
			default: {
				if (i % 2 != 0) { // 짝수는 보지 않는다.
					while (cnt < 1) {
                    	// 3부터 i의 반까지
						for (int j = 3; j <= i / 2; j++) { 
                         	// i나누기 j가 나누어 떨어진다면
							if (i % j == 0) {
                            	// cnt 증가, cnt가 1이라면 while문탈출
								cnt++; 
							}
						}
                        // 작업 수행 후 cnt가 0이라면 그 수 출력
						if (cnt == 0) { 
							System.out.println(i);
							break; // while문 탈출
						}
					}
					cnt = 0;
				}
			}
			}
		}
	}

}

예제 입력 결과

채점 결과

후.. 이번에도 이중 for문에 while문까지 써서 그런가 시간 초과 당했다...
코드를 원초적으로 짜서 효율이 매우 안 좋은가 보다..
백준 문제 풀면서 내가 모르는 알고리즘 공부도 같이 해야겠다😔

 

 

---

 

2024/01/12 수정

 

최근 백준 풀다가 안 된 문제들을 다시 풀어보는 중인데.. 찾아보니 다른 사람들은 거의 배열을 사용했다.

난 배열 for문 돌리면서 초기화하고 값 넣는 게 더 시간 오래 걸릴줄 알고 배열은 손도 안 댔는데...

 

그리고 에라토스테네스의 체 라는 수학 기법을 사용했더라.

 

그게 뭐냐면.. 1부터 100까지 다 적어 놓고, 2의 배수 삭제하고 3의 배수 삭제하고 5의 배수 삭제하고

그런식으로 가지치기 해서 최종 남는 애들을 소수로 취급하는 것이다.

 

그래서 참고하여 새 코드를 작성했다.

 

 

새롭게 작성한 코드

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		
		//입력 받기
		Scanner sc = new Scanner(System.in);
		int start = 0, end = 0;
		start = sc.nextInt();
		end = sc.nextInt();
		
		//배열 초기화
		int[] arr = new int[end+1];
		for(int i=0; i<=end; i++) arr[i] = 0;
		arr[1] = 1;	//1은 소수가 아님

		//각각의 수의 배수들에 1을 채움
		for(int i=2; i<=end; i++) {
			for(int j=2; i*j<=end; j++)
				arr[i*j] = 1;
		}

		//최종 남은 수들 출력
		for(int i=start; i<=end; i++)
			if(arr[i] != 1) System.out.println(i);
		
	}
}

 

 

이렇게 하니 for, while, if 문을 활용했을 때보다 코드가 훨씬 간결해졌다.

처음에는 배열의 모든 원소들을 0으로 초기화하고, 소수가 아닌 수들을 1로 바꾸는 방식이다.

 

 

재채점 결과

 

 

 

문제 맞히기까지 기나긴 여정이었다... 코딩을 하면서 수학 공식도 알아가다니..^^ 일석 이조이다..