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

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

1929번: 소수 구하기

 

---

중학교 다닐 때

수학시간에 선생님이 

이건 솟수로 발음해야한다고 하시면서...설명해줬던게 갑자기 생각이 났다

 

1보다 큰 정수 중 1과 자기자신만을 약수로 가진 수를 소수라고 하는데

 

X	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50

대충 이런 표를 하나 그린 다음

2부터 시작해서 2로 나누어 떨어지는 수는 X를 친다(2는 제외)(X는 소수가 아니라는 뜻)

X	2	3	X	5	X	7	X	9	X
11	X	13	X	15	X	17	X	19	X
21	X	23	X	25	X	27	X	29	X
31	X	33	X	35	X	37	X	39	X
41	X	43	X	45	X	47	X	49	X

2로 나누어지는 수를 모두 X쳤으면

X가 아닌 다음 수인 3을 잡고

3으로 나누어 떨어지는 수를 또 X 친다

X	2	3	X	5	X	7	X	X	X
11	X	13	X	X	X	17	X	19	X
X	X	23	X	25	X	X	X	29	X
31	X	X	X	35	X	37	X	X	X
41	X	43	X	X	X	47	X	49	X

이런식으로 ... 끝까지 반복하면

소수만 남게 된다.

 

나는 간단하게 이 방법을 그대로 코드로 옮겼다

---

코드

import java.util.Scanner;

public class P1929 {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		int m=sc.nextInt();
		
		boolean[] p =new boolean[m+1];
		
		for(int i=2;i<=m;i++) {
			p[i]=true;
		}
		p[0]=false;
		p[1]=false;
		
		for(int i=2;i<=m;i++) {
			
			if(p[i]==true) {
				for(int j=i*2;j<=m;j+=i) {
					p[j]=false;
				}
			}
			
		}
		
		for(int i=n;i<=m;i++) {
			if(p[i]==true)
				System.out.println(i);
		}
	}

}

1은 소수가 아니라는걸 깜빡했다가 

자꾸 틀려서 당황스러웠다.