[JAVA] 백준 알고리즘 1929번 문제풀이 (소수 구하기)

 

 

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

 

● 소수 구하기

문제 (1929번)

​

Q. M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

 

 

 

 

 

 

 

 

 

import java.util.*;
//1978번
public class Main {

	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		boolean[] check = new boolean[m+1];
		check[0] = check[1] = true;
		for(int i=2; i<=m;i++) {
			if(check[i]==true) {
				continue;
			}
			for(int j=i+i; j<=m; j=j+i) {
				check[j]=true;
			}
		}
		for( int i=n; i<=m; i++) {
			if(check[i]==false) {
				System.out.println(i);
			}
		}
	}

}

​

↓ 소스풀이 ↓

​

n이상 m이하의 소수를 구하기위해 n과 m을 입력받아줍니다.

check[]배열을 생성해서 소수인지 아닌지를 boolean타입으로 true,false로 구분해줍니다.

true일경우는 소수가 아니고, false일경우는 소수일때입니다.

시작전, 자연수 0과 1은 소수구분이 없기에 true로 셋팅해주었습니다.

for문을 사용해서 2부터 입력받은 m까지 반복해주고,

check을 i부터 시작해서 true일경우, 어차피 소수가 아니므로 continue해줍니다.

다음 for문에는 2의 배수라면 당연히 약수로 2가 들어갑니다.

예를들어, 6의 약수는 1,2,3,6입니다. 즉 2가 약수로 들어가기에 2의 배수들은 모두 소수가아니기에

true로 바꿔줍니다.

마지막으로 출력해주는 반복문을 넣어주고 false(소수)인경우만 출력해줍니다.

 

 

 

 

< 백준알고리즘 강의를 보고 참고하였습니다! >

 

 

---