백준 BaekJoon 1929번: 소수구하기 [Java] 자바

2020 / 07 / 11

---

오늘은 백준 1929 소수 구하기 문제풀이 

알고리즘 해답을 알려드리겠습니다

백준 1929 자바

---

우선은 소수란 7과 같이 나눌 수 있는 수가 1과 자기 자신밖에 없는 수를 말합니다.

 

위키백과 왈...

소수(素數, [소쑤])는 수학에서 1과 그수 자신 이외의 자연수로는 나눌 수 없는, 1보다 큰 자연수이다.

소수(小數, [소수]) 수학에서 소수점을 찍어 나타낸 실수이다.

소수(小數)는 수학에서 0보다 크고 1보다 작은 수이다.

---

		Scanner scan = new Scanner(System.in);
		System.out.println("숫자를 입력해주세요.");
		int M = scan.nextInt(); // 작은 값
		int N = scan.nextInt(); // 큰 값
		
		int count = 0; // 소수확인을 위한 카운트 변수 선언
		
		for(int i = M; i <= N; i++) {
		for(int j = 2; j < i; j++) {
			if(i % j == 0)
				count ++; // i 의 값이 j로 나누어 져 해당 값은 소수가 아님
		}		
			if(count == 0 && i !=0) {
			System.out.println(i);
			}
			count = 0; // 다시 소수를 확인하기 위해 루프 마지막 카운트 초기화
		}

백준 1929 자바

 

크게 어려운 부분이 없었던 문제였는데...

정답률이 27%뿐이라는게 조금 아이러니했습니다.

오히려 저는 남들 다 맞추는 정답률 60% 이상 문제들이 더 어려웠던 거 같습니다. ㅠㅠ

---

카운트 변수를 선언하여, if 문을 통해 해당 수가 소수인지 판단하였습니다.

소수일 경우 count를 하나씩 더해주었으며, count가 0일 경우 해당 수는

1과 자기 자신밖에 나눠지는 수가 없다고 판단하여, i 번째에 해당하는

수를 출력하게끔 알고리즘을 작성하였습니다!!

 

 

해당 풀이에 개선방안 있으시면 언제든 알려주시면 감사하겠습니다!!

 

시간오류가 나옴 정답률이 낮은 이유가 있었음

▼

찾아보니 에라토스테네스의 체라는 시간복잡도가 낮은

소수 구하는 방식이 있음

▼

위와 같이 소수의 배수를 없애주는 방식이 있음 이를 통해서 빠른 시간에 소수만 출력할 수 있었다. 궁금하면 아래 링크로 들어가서 확인하자. 이제 다시 푼 코드 이다.

출처 링크 : bit.ly/38LOUsY

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

참고블로그 : bit.ly/38Q98SF  /  bit.ly/35KOG3w

---

import java.util.Scanner;

public class TemplateA {
	public static void main(String[] args){

		int i,j; // 반복문 변수 선언
		Scanner scan = new Scanner(System.in);
		System.out.println("숫자를 입력해주세요.");
		final int M = scan.nextInt(); // 작은 값
		final int N = scan.nextInt(); // 큰 값
		
		int [] arr = new int [N + 1];
		//큰 값에 맍는 배열 크기를 선언해준다.
		
		for(i = 0; i <= N; i++) {
			arr[i] = 0;
		}//배열값 초기화
		
		
		arr[1] = 1; // 1은 소수가 아님
		//때문에 소수의 배수들을 모두 1로 바꿈
		
		for (i = 2; i < N + 1; i++) {
			if(arr[i] == 0) { // 배열값이 0이면 소수의 가능성 있음
				if((int)Math.pow(i, 2) > 1000000){
					break; // 해당 i의 값을 제곱하여 범위가 넘어가면 비교 불필요 종료
				}else {
					for (j = (int)Math.pow(i,2); j < N + 1; j = j + i) {
						// j 값은 i의 제곱수로 초기화함
						// 최대범위까지 체크
						// 이후 j를 다시 배수값을 더해서 초기화
						arr[j] = 1; 
						// 1은 소수가 아님
						// 1이 되는 값은 출력안함
					}// j ->for문 종료
				}
			}
		}// i ->for문 종료

		
		//초기 주어진 작은수 부터 큰수까지 1이 아닌 위치를 출력
		for (i = M; i < N + 1; i++) {
			if(arr[i] != 1) {
				System.out.println(i);
			}
		}
			
	}
}