오늘은 에라토스테네스의 체에 대해 알아볼 겁니다.
그래서 에라토스테네스의 체가 뭔데? 처음엔... 발음도 힘들었다
뭔데 소수판별만 나오면 에라토스테네스의체를 사용해서 풀어야 효율적이라고 나오고
Chatgpt에 물어봐도 이렇게 답변해주는건데?
에라토스테네스의 체
정의를 보면 이렇게 설명한다
2부터 시작하는 자연수들 중에서 소수(약수가 1과 자기 자신인 수)를 찾아내는 방법입니다. 작은 수부터 차례대로 배수들을 제외해가면서 소수를 찾아내는 방법입니다
조금 더 자세히 설명을 하면 2부터 20까지의 자연수 중에서 소수를 찾는다고 하면,
첫번째 2 다음 2, 4, 6, 8, 10 ... (제외)
두번째 3 다음 3, 6, 9, 12 ...(제외)
세번째 4 첫번째에서 (제외)당함
네번째 5 다음 10, 15, 20 (제외)
흠... 뭔가 알듯 말듯 하면서도 이해되는거 같으면서도 안되는거 같으면서도 그런느낌... 압니다.
저도 그랬거든요 ㅎㅎ;;
코드로 보면서 이해해봅시다
여기서 진탱임... 정신 차리고 봐야함
2부터 20까지의 자연수중에 소수를 찾아보시오.
일단은 함수부터 만들어 봅시다.
// 매개변수로 number 받고 찾은 소수를 배열로 리턴합니다.
func findPrime(_ number: Int) -> [Int] {
return []
}
let result = findPrime(20)
print(reuslt)
코드를 작성해보면
func findPrime(_ number: Int) -> [Int] {
// repeating을 사용해서 number+1 만큼의 배열 만들주기 --> 왜? for문을 돌릴때 2부터 시작할거니까
var isPrime = Array(repeating: true, count: number+1)
print(isPrime)
return []
}
자! 여기서 보면
Array(repeating: true, count: number+1)
이부분이 조금 이상하다고 생각들지 않으신가요?
이상하다고 생각 들으셨다면 당신은 지니어스!
바로 count 부분에 number + 1이 되어있기 때문입니다.
처음 봤을때 이거 뭐야... 왜 쓸데없이 + 1을 하는거야 라고 생각했지만 제 오만이고 착각이었습니다. 흑흑
이부분을 조금 뜯어보면 이유가 있습니다.
바로 !!
2부터 시작하는 자연수들 중에서 소수(약수가 1과 자기 자신인 수)를 찾아내는 방법입니다
2부터 시작한다는것이 키포인트 입니다. 2부터 시작하기 때문에 for문을 돌릴때 2...20으로 시작한다는거죠!!
func findPrime(_ number: Int) -> [Int] {
// repeating을 사용해서 number+1 만큼의 배열 만들주기 --> 왜? for문을 돌릴때 2부터 시작할거니까
var isPrime = Array(repeating: true, count: number+1)
print(isPrime)
for i in 2...number {
}
return []
}
/*
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
*/print 몇개 나왔는지 갯수 세지 말아여... 그런건 제가 할게요 ㅠ
즉, 총 21개의 배열 요소가 만들어 집니다.
다음 코드를 작성해보겠습니다.
func findPrime(_ number: Int) -> [Int] {
// repeating을 사용해서 number+1 만큼의 배열 만들주기 --> 왜? for문을 돌릴때 2부터 시작할거니까
var isPrime = Array(repeating: true, count: number)
print(isPrime)
// 소수를 담아줄 배열
var primes: [Int] = []
for i in 2...number {
if isPrime[i] == true {
// isPrime[i]가 true라면 append를 통해 담아준다.
primes.append(i)
for j in stride(from: i*i, through: number, by: i) {
isPrime[j] = false
}
}
}
return []
}
자 그렇다면 코드를 뜯어보겠습니다.
1. 일단 소수를 담아줄 변수를 만들어줍니다
// 소수를 담아줄 배열
var primes: [Int] = []흠... 참 쉽죠?!
2. isPrime[i]가 == true 일때 append를 해줍니다. 그 이유가 나옵니다.
if isPrime[i] == true {
primes.append(i)
for j in stride(from: i*i, through: number, by: i) {
isPrime[j] = false
}
}
제일 중요한 부분입니다 집중
자 하나씩 가보겠습니다.
for i in 2...number {
if isPrime[i] == true {
primes.append(i)
for j in stride(from: i*i, through: number, by: i) {
isPrime[j] = false
}
}
}1) i가 2일때 :
if isPrime[2] == true {
primes.append(2)
for j in stride(from: 2*2, through: number, by: 2) {
isPrime[j] = false
}
}그렇다면 isPrime[j]에는 4부터 +2 씩 증가하면서 값이 true에서 false로 바뀌게 됩니다.
/*
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
*/
였던것이
/*
[true, true, true, true, false, true, false, true, false, true, false, true, false, true, false, true, false, true, false, true, false]
*/
이렇게 바뀝니다.
2) i 가 3일때:
if isPrime[3] == true {
primes.append(3)
for j in stride(from: 3*3, through: number, by: 3) {
isPrime[j] = false
}
}
자. 현재 isPrime배열의 상태는
[true, true, true, true, false, true, false, true, false, true, false, true,
false, true, false, true, false, true, false, true, false]이렇게 되어있습니다. 위의 코드로 보면 isPrime[9]부터 +3 씩 더해가면서 false로 바꿔주는 작업을 합니다.
[true, true, true, true, false, true, false, true, false, false, false,
true, false, true, false, false, false, true, false, true, false]이렇게 바뀝니다.
현재 2,3만 들어가있는 상태 인데도 false 밭이 되어버렸군요... 그렇다면
이어서 4와 5를 넣어보겠습니다.
3) i 가 4일때 :
.... 첫번째 i가 2라서.. 벌써 false로 되어있네요
if isPrime[i] == true {
primes.append(i)
for j in stride(from: i*i, through: number, by: i) {
isPrime[j] = false
}
}그래서 if isPrime[i] == true {} 를 실행하지 못합니다.
4) i가 5일때:
현재 isPrime의 상태입니다.
[true, true, true, true, false, true, false, true, false, false, false,
true, false, true, false, false, false, true, false, true, false]
일단 첫번째 난관 다섯번째 인덱스가 true냐? 네 맞습니다.
if isPrime[5] == true {
primes.append(5)
for j in stride(from: 5*5, through: number, by: 5) {
isPrime[j] = false
}
}i = 5가 들어갑니다.
그렇지만
for j in stride(from: 5*5, through: number, by: 5) {
isPrime[j] = false
}시작이 25부터 이기 때문에 시작부터 number(20)를 넘어섭니다. 그래서 for j문은 실행되지 않습니다.
추후 stride관련해서 다뤄보겠습니다.
이런식으로 하나씩 지워지게 되고 true인것만 primes에 담겨집니다.
func findPrime(_ number: Int) -> [Int] {
// repeating을 사용해서 number+1 만큼의 배열 만들주기 --> 왜? for문을 돌릴때 2부터 시작할거니까
var isPrime = Array(repeating: true, count: number+1)
print(isPrime)
// 소수를 담아줄 배열
var primes: [Int] = []
for i in 2...number {
if isPrime[i] == true {
primes.append(i)
for j in stride(from: i*i, through: number, by: i) {
isPrime[j] = false
}
}
}
return primes
}
let result = findPrime(20)
print(result)
/*
[2, 3, 5, 7, 11, 13, 17, 19]
*/
이렇게 소수 판별을 하는 방법을 에라토스테네스의 체 라고 합니다.
긴 글 읽어주셔서 감사합니다. 고생하셨습니다.
한줄 평 : 이해하니 이렇게 쉬운걸 왜 그전까지 for문으로 싸우고 있었나...
주의! 여기서 부터는 읽지 말것
번외로) 난 호기심이 많은 개발자!!
그렇다면 의문이 듭니다. 그렇다면 count: number만 적으면 어떻게 될까?
제가 해봤습니다.
네 어김없이 index out of range가 나왔습니다.
조금 더 궁금해서 해봤습니다.
func findPrime(_ number: Int) -> [Int] {
// count: number를 넣어봤습니다.
var isPrime = Array(repeating: true, count: number)
print(isPrime)
// 소수를 담아줄 배열
var primes: [Int] = []
for i in 0..<number {
if isPrime[i] == true {
primes.append(i)
for j in stride(from: i*i, through: number, by: i) {
isPrime[j] = false
}
}
}
return primes
}
let result = findPrime(20)
print(result)
/*
Stride size must not be zero
*/
number의 갯수 만큼 for문을 돌릴려고 0..<number를 해줬지만, 또 막히는 부분이
for문안에 stride 함수가 있구나... stride 함수는 by: 만큼 증가하는 것인데 0이 오면... 증가를 할수 없는데...
오늘의 결론: 하지 말라고 한것은 하지 말자!
'알고리즘' 카테고리의 다른 글
| 프로그래머스 LV.1 옹알이(2) 스위프트 (0) | 2023.05.07 |
|---|---|
| 프로그래머스 LV.1 숫자 짝꿍 스위프트 (0) | 2023.05.05 |
| 프로그래머스 LV.1 기사단원의 무기 (0) | 2023.05.03 |
| 프로그래머스 LV.1 덧칠하기 스위프트 (0) | 2023.05.02 |
| 프로그래머스 LV.1 카드 뭉치 (0) | 2023.04.30 |