Algorithm3 [알고리즘] 에라토스테네스의 체 [알고리즘] 에라토스테네스의 체 고대 그리스의 수학자이자 지리학자인 에라토스테네스가 고안한 소수를 찾는 방법으로 2를 제외한 2의 배수, 3을 제외한 3의 배수, 5를 제외한 5의 배수의 순서로 수를 지워나가 끝에 남는 수가 소수이다. 마치 체로 치듯이 걸러낸다고 하여 '에라토스테네스의 체' 라고 불린다. 이는 자연수 N에 대해서 그 이하의 수 중에서 소수를 찾는 가장 빠른 방법이다. 방법 1부터 N까지 소수를 구하고자 하는 구간의 모든 수를 쭉 나열한다. 우선 소수도, 합성수도 아닌 유일한 자연수 1을 제거한다. 남은 수 가운데 가장 작은 수를 제외한 배수를 모두 지운다. 3번 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다. 위의 2번 과정을 조금 더 풀어서 흐름이 어떻게 진행되는지 살펴보자... 2021. 9. 16. [알고리즘] 소수 판별법 [알고리즘] 소수 판별법 소수(prime number) 란? 소수 (Prime Number)는 1과 자기 자신으로만 나누어떨어지는 자연수를 뜻한다. 좀 더 수학적인 표현을 사용한다면 정수 p > 1의 양수인 약수가 1과 p뿐일 때, p를 소수라고 부른다. 가령 자연수 7의 경우 1과 7로만 나누어 떨어지므로 소수이다. 다른 예로 자연수 4의 경우 1, 2, 4로 나누어 떨어지므로 소수가 아니다. 그렇다면 소수에 대해서 알았으니 소수판별법에 대해서 알아보자. 소수판별법 수론에서, 소수판별법은 어떤 자연수 N이 소수인지 합성수인지를 판별하는 알고리즘들을 말한다. 추가로, 합성수(合成數, composite number)는 1보다 큰 자연수 중에서 소수가 아닌 수로 합성수의 특징은 약수의 개수가 3개 이상이고 .. 2021. 9. 13. [탐색 알고리즘] lower_bound, upper_bound [탐색 알고리즘] lower_bound, upper_bound lower_bound, upper_bound는 기본적으로 이진 탐색을 기반으로 하기 때문에 탐색하고자 하는 수열(원소들)이 오름차순으로 정렬되어 있어야 합니다. 이렇게 정렬된 리스트에서 특정 값 위치를 찾을 때 사용합니다. 그렇다면 특정 값이 무엇인지 밑에 설명을 보시면 알 수 있습니다. 1. lower_bound : 크거나 같은 수 중에서 첫 번째 수 (특정값) 2에 대한 lower_bound 즉 , 2와 같거나 큰 수중 가장 작은 인덱스를 찾고자 한다면 그림에서 보이는 바와 같이 1번 째입니다. [소스 코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include using n.. 2020. 7. 18. 이전 1 다음
