[수학] 소수 관련 알고리즘

알고리즘 문제를 풀다보면 소수 판별에 대한 개념이 많이 나오곤 한다. 

소수는 양의 약수가 1과 자기 자신 뿐인 1보다 큰 자연수로 정의된다. 

규칙성이 증명이 안되서 참 난해한 부분이 많다. 정수론에서 매우 중요한 역할을 담당한다.

 

이진코드나 수학적 특성을 이용한 알고리즘 문제를 풀 때 생각보다 많이 사용되어서 정리해보자 

참고 사이트 : 코드와 함께 정리가 잘 되어있다. 이거보다 잘할 자신이 없어서 문제풀이만 올린다. http://ledgku.tistory.com/61

요약 하자면, "모든 자연수는 소수들의 곱으로 표현된다."

1. 소수는 구하고자하는 값의 root 만큼만 체크하면 확인 가능하다.(에라토스테네스의 접근)

 * 연산 횟수 sqrt(n-2) 

2. 구하고자 하는 수 이하의 배수 값을 저장하면서 걸러낸다. (에라토스테네스의 체)

 * 저장 공간이 필요 

3. 주어진 수가 소수인지 아닌지 판별만 할 경우 (에라토스테네스의 접근)

   주어진 수까지의 모든 소수를 구하기 위해서는 (에라토스테네스의 체)

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

소수 구하기

답 ------------------

https://github.com/inspire12/Algorithm/tree/master/acm1929