소수 출력

사용자에게 입력받은 int형 정수 N까지의 모든 소수를 출력해보자.

소수(Prime Number)란 1보다 큰 수 자연 중에 1과 자기 자신만을 약수로 가지는 수이다.

대충 나열해보면 2, 3, 5, 7, 11, 13, 17, 19,............이다.

 

N = 100이라면 어떻게든 찾아낼 수 있겠지만, N = 100000이라면 여간 힘든 일이 아닐 것이다.

어떻게 하면 소수를 가려낼 수 있을까?

 

처음에 생각한 방법은 이랬다.

 

1. 10 이하에서는 2, 3, 5, 7만 출력한다. 왜냐하면 10 이하에서는 2, 3, 5, 7만 소수이므로.

 

2. 10 이상부터는 2, 3, 5, 7로 나누어 떨어지는 수를 제외하고 출력한다. 왜냐하면 10 이상에서는 2, 3, 5, 7로

나누어 떨어지지 않는 수가 소수이므로.

 

자바 코드로 옮겨보면

 

시험삼아 100까지만 출력함

 

결과를 출력해보니 제대로 소수를 출력한다

 

하지만 이 방법은 조건문으로 모든 것을 해결하려고 했기 때문에, 주먹구구식이 아닌가 하는 생각이 들어서 다르게 생각해보기로 했다.

 

 

약수에 대해서 조금 더 생각해보면, 어떤 정수 N의 약수는 자기 자신을 제외하고 최대 2/N 보다 클 수 없다.

예를 들어 8의 약수는 1, 2, 4, 8로서, 최대 8/2 = 4 보다 클 수는 없다는 것이다. 

그렇다면 정수 N의 약수를 조사해볼 때, N까지 숫자를 나눠가며 약수를 구할 필요 없이 N/2 까지만 나눠보면

약수의 개수를 알 수 있을 것이다.

 

이 생각을 의사 코드로 표현해보면,

 

어떤 정수 N에 대하여,

Prime Number = true

for i = 2 to N/2 

  if N % i == 0

    Prime Number = false

 

정도로 표현할 수 있을 것 같다.

 

그런데 소수를 찾는 방법인 에라토스테네스의 체에 대해서 위키백과에 이렇게 나와있다.

출처: https://ko.wikipedia.org/wiki/소수_(수론)

N/2 까지도 갈 것도 없이 √N까지만 확인해보면 된다는 말인데, 즉 약수를 이루는 수는 어떤 수의 곱으로 표현할 수 있으며 (예: 4의 약수 중에 2는 1 * 2로 표현 가능) 만일 곱으로 표현하는 경우, 하나가 √N보다 크다면 반드시 하나는 √N보다 작아야 한다는 것이다. 

(여담이지만 N/2와 √N 사이의 크기는, N > 4 인 경우부터 N/2 > √N이다)

 

이해가 잘 안 되지만 어쨌든 √N까지만 확인해도 된다는 것만 기억하기로 했다.

 

의사 코드로 표현해보면,

 

어떤 정수 N에 대하여,

Prime Number = true

for i = 2 to √N

 if N % i == 0

    Prime Number = false

 

반복문의 범위가 √N 까지라는 것은 i≤√N이고, 정리하면 i²≤N으로 표현할 수 있을 것이다.

이를 바탕으로 자바 코드로 옮겨보면

 

시험삼아 100까지만 출력함

 

 

 

위와 같이 만들 수 있을 것 같다.

 

실제로 프로그램 결과를 보면

 

성공적으로 잘 나오는 것을 확인할 수 있었다.