소수판별 (2) 썸네일형 리스트형 [BOJ] 백준 4948 베르트랑 공준 (Swift) 문제 https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 풀이 n보다 크고 2 * n 보다 작거나 같은 소수의 개수를 출력하는 문제입니다. 에라토스테네스의 체 알고리즘을 사용하여 소수들을 구할 수 있습니다. n이 최대 123,456 이므로, 에라토스테네스의 체 알고리즘을 사용하여 123,456 * 2 만큼의 소수들을 한 번에 구해줍시다. 그 이후, n + 1 부터 2 * n 까지의 소수들의 개수를 출력해주면 됩니다. 고차함수 filter를 .. [알고리즘] 에라토스테네스의 체 (Swift) 에라토스테네스의 체 에라토스테네스의 체 알고리즘은 고대 그리스 수학자인 에라토스테네스가 만들어낸 소수를 찾는 알고리즘 입니다. 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체' 라고 불린다고 하네요. 방법 예를 들어 1 ~ 100까지의 숫자 중 소수를 찾는다고 생각해 봅시다. 먼저, 1부터 100까지의 수를 쭉 써줍니다. 코드상으로는 101만큼의 크기인 Boolean Array를 true로 초기화를 해줬습니다. 표로 나타내보면, 이렇게 나타낼 수 있겠네요. 1은 소수가 될 수 없기에 제거해줍니다. 2를 제외한 2의 배수를 제거합니다. 3을 제외한 3의 배수를 제거합니다. 이제 다음 차례로는 4를 제외한 4의 배수를 제거해야겠죠? 하지만 4는 2의 배수이기 때문에, 이미 다 지워졌습니다. 다음.. 이전 1 다음
