나의 개발일지

'에라토스테네스의 체' 란? '에라토스테네스의 체'란, 2부터 시작하는 양의 정수들 중에서 소수(prime number)인 것을 찾아내는 알고리즘 중 하나입니다. 이 알고리즘은 2부터 시작하여, 그 다음 소수의 배수를 모두 지워가면서 소수를 찾아내는 방식으로 동작합니다. 먼저, 2부터 n까지의 모든 정수를 배열에 저장합니다. 그리고 배열에서 2를 제외한 2의 배수를 모두 지웁니다. 다음으로, 배열에서 3을 제외한 3의 배수를 모두 지웁니다. 이렇게 배열에서 지워지지 않은 가장 작은 수를 다음 소수로 간주하고, 그 수를 제외한 그 수의 배수를 모두 지웁니다. 이 과정을 반복하여, 배열에서 지워지지 않은 수가 소수가 됩니다. 예를 들어, 2부터 10까지의 소수를 찾는 과정을 살펴보겠습니다. 먼저, 2를 제외..

실버Ⅴ https://www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 풀이 방법 우선 이 문제는 M과 N을 입력받고, M과 N 사이의 수 중 소수를 찾아 그 소수들을 모두 합한 값과, 그 소수 중 가장 작은 값을 각각 출력하는 문제이다. 먼저 나의 경우 N의 값을 입력받으면서 배열의 크기가 최대 N으로 고정되기 때문에 10000의 원소를 갖는 배열을 만드는 방법이 아닌, 동적할당을 이용해 배열을 할당했다. 만약 동적할당의 사용법을 모른다면 동적할당에 관한 글을 아래에 ..