백준 1978번 문제풀이 - 소수 찾기

백준 1978번 문제

 

 

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

1978번: 소수 찾기

 

0.1, 0.2과 같은 이런 소수를 말하는 것이 아니라 1을 제외한 1과 자신만을 약수로 갖는 자연수를 말한다.

말 그래도 소수인지 아닌지를 판별하는 문제이다.

 

소수를 판별하기 위해서 2부터 쭉 나눠보면서 확인을 해야 하는데 한 블로그의 글을 보고 모든 수를 나눠보지 않고

확인할 수 있었다.

방법은 이와 같다.

판별하는 number의 수를 A * B인 합성수로 라고 볼 때

1 ≤ A,B < number와 같은 부등식을 세울 수 있다.

A, B 두 수가 number의 제곱근보다 크게 되면

A * B > number가 돼버려서 식과는 모순이 생기게 된다.

그러므로 A, B 둘 중 하나는 number의 제곱근보다 작아야된다는 것을 알 수 있고 number의 제곱근과 같거나 작은 수까지만 확인해보면 된다는 것을 알 수 있다.

 

 

 

 

 

코딩

  

 

 

 

 

결과

 

 

 

 

 

느낀 점

백준 문제에서도 수학파트의 문제라서 수학적인 사고를 많이 필요로 했다. 처음에는 소수를 2, 3, 5, 7로만 나눠봐서 나눠지지 않으면 다 소수이지 않을까하는 안일한 생각을 했다. 좀 더 생각해보면 11*11의 경우는 소수가 아니기 때문에 모든 수를 나눠봐야된다는 것을 알 수 있었다.

 

 

 

 

 

참고 : https://st-lab.tistory.com/80

[백준] 1978번 : 소수 찾기 - JAVA [자바]