정보처리기능사 실기 알고리즘#16 - 소수 알고리즘!

정보처리기능사 열여섯번째 유형 소수 알고리즘에 대해서 정리해봅니다.

Ewww! Gooos!

정보처리기능사 실기 알고리즘 요점정리#16 - 소수구하는 알고리즘

1. 소수란?
- 소수는 1과 자기자신으로만 나눠지는 수를 이야기한다.

2 3 5 7 11 13 17 같은 느낌상? 좀 짜증나는 수들!

2. 소수 알고리즘 원리

- 소수는 1과 자기자신으로만 나눠져야 한다. -> 자기 자신뺴고 그 어떤수의 배수여도 안된다! ->

배수가 아니다? 나누어 떨어지지않는다 = 나머지가 0이 아니다. MOD값이 0이 아니여야 한다. -> A MOD B = 0 이면 A는 B의 배수이므로 A는 소수가 아니다!

3. 소수구하는 알고리즘

: 2의 배수에서부터 시작해서 (자기자신-1)까지의 모든수 각각 나눠봐서 나머지가 0인 적이 한번도 없으면 그 수는 소수가 된다.

예를들어 17이면 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 을 각각 모두 나눠서 나머지가 0인적이 한번이라도 있으면 그수의 배수이므로 패스하고 다음수로 넘어가게 만들면 된다. (위같은경우는 0인적이한번도 없으므로 소수!)

* FYI

1은 소수인가? ㄴㄴ

2는 소수인가? ㅇㅇ