알고리즘 - 프로그래머스 소수찾기 (Swift)

알고리즘 - 프로그래머스 소수찾기 (Swift)

2020. 7. 1. 16:03ㆍAlgorism

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

제한 조건

n은 2이상 1000000이하의 자연수입니다.

입출력 예

소수 : 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다 (나무위키)

쉬울줄 알았는데... 시간초과가 계속 발생하니... 어렵네요 ㅠㅠ

푸는 방법은 시간초과를 벗어나는게 핵심이에요.

그러기 위해서는 에라토스테네스의 체 (나무위키)를 사용해야 하는데요.

소수를 증명 하기 위해서는 n이라는 숫자를 2, 3, 5 등으로 나누어서 확인을 해야 하는데.

위와 같이 하나의 값들을 모두 for-in문을 사용하게되면 불필요한 작업 때문에 연산 속도가 느려저서

위의 알고리즘 테스트에서는 통과를 할 수 없습니다.

그래서 위의 에라토스테네스의 체라는 방법을 써야하는데요.

간단하게 말하자면

먼저 Array 지정된 갯수의 배열을 생성해요. (빙고판 & 모기장 처럼)

그리고 for문을 실행해서

2라는 숫자가 들어오면 2를 제외한 모든 배수를 제거

3라는 숫자가 들어오면 3를 제외한 모든 배수를 제거

5... 위와 동일

이렇게 진행하면 n이라는 숫자를 나누는 것보다 불필요한 동작을 하지 않게 되기 때문에 효율이 좋아질 수 있습니다.

- 연산을 해야할 갯수가 많아질 수 록 효율이 더 좋아집니다. (아래 100개의 연산 로그 창 참고)

아래 로그를 참고하시면 이해가 더 쉬울 수도...? 있을거에요!

# 추가내용

참고로 소수를 구하는 공식으로 입력받은 숫자의 제곱근 까지의 숫자로 나눈는 방법까지 추가하면 더욱 빠른 연산을 진행 할 수 있습니다.

func stride는 사용하지 않고 for-in문을 사용 하셔도 무방합니다.

import Foundation

func solution(_ n:Int) -> Int {
    
    var primeCount = 0 // 소수 개수
    var numberArray = Array(repeating: true, count: n+1) // 입력 받은 숫자 배열
    // 숫자배열이 0부터 시작하기 때문에 +1을 진행합니다.
    // 1~10까지의 소수를 구할때 배열 [0,1,2,3,4,5,6,7,8,9,10]
    
    // 0, 1은 제외
    for num in 2...n {
        print("\n--> num \(num), isPrime = \(numberArray[num])")
        
        if numberArray[num] {
            primeCount += 1
            
            // 다음 배수부터 연산 진행
 			// for 2 in stride(from: 2*2, through:11, by: 2)
            // for 5 in stride(from: 5*2, through:11, by: 5)
            for index in stride(from: num*2, through:n, by: num ) {
                numberArray[index] = false
                print("is not prime num \(index), isPrime = \(numberArray[index])")
            }
        }
    }
    
    return primeCount
}


print("\n\n--> result is prime count = \(solution(10))")

--> num 2, isPrime = true
is not prime num 4, isPrime = false
is not prime num 6, isPrime = false
is not prime num 8, isPrime = false
is not prime num 10, isPrime = false

--> num 3, isPrime = true
is not prime num 6, isPrime = false
is not prime num 9, isPrime = false

--> num 4, isPrime = false

--> num 5, isPrime = true
is not prime num 10, isPrime = false

--> num 6, isPrime = false

--> num 7, isPrime = true

--> num 8, isPrime = false

--> num 9, isPrime = false

--> num 10, isPrime = false


--> result is prime count = 4

숫자 100까지의 연산시 로그

--> num 2, isPrime = true
is not prime num 4, isPrime = false
is not prime num 6, isPrime = false
is not prime num 8, isPrime = false
is not prime num 10, isPrime = false
is not prime num 12, isPrime = false
is not prime num 14, isPrime = false
is not prime num 16, isPrime = false
is not prime num 18, isPrime = false
is not prime num 20, isPrime = false
is not prime num 22, isPrime = false
is not prime num 24, isPrime = false
is not prime num 26, isPrime = false
is not prime num 28, isPrime = false
is not prime num 30, isPrime = false
is not prime num 32, isPrime = false
is not prime num 34, isPrime = false
is not prime num 36, isPrime = false
is not prime num 38, isPrime = false
is not prime num 40, isPrime = false
is not prime num 42, isPrime = false
is not prime num 44, isPrime = false
is not prime num 46, isPrime = false
is not prime num 48, isPrime = false
is not prime num 50, isPrime = false
is not prime num 52, isPrime = false
is not prime num 54, isPrime = false
is not prime num 56, isPrime = false
is not prime num 58, isPrime = false
is not prime num 60, isPrime = false
is not prime num 62, isPrime = false
is not prime num 64, isPrime = false
is not prime num 66, isPrime = false
is not prime num 68, isPrime = false
is not prime num 70, isPrime = false
is not prime num 72, isPrime = false
is not prime num 74, isPrime = false
is not prime num 76, isPrime = false
is not prime num 78, isPrime = false
is not prime num 80, isPrime = false
is not prime num 82, isPrime = false
is not prime num 84, isPrime = false
is not prime num 86, isPrime = false
is not prime num 88, isPrime = false
is not prime num 90, isPrime = false
is not prime num 92, isPrime = false
is not prime num 94, isPrime = false
is not prime num 96, isPrime = false
is not prime num 98, isPrime = false
is not prime num 100, isPrime = false

--> num 3, isPrime = true
is not prime num 6, isPrime = false
is not prime num 9, isPrime = false
is not prime num 12, isPrime = false
is not prime num 15, isPrime = false
is not prime num 18, isPrime = false
is not prime num 21, isPrime = false
is not prime num 24, isPrime = false
is not prime num 27, isPrime = false
is not prime num 30, isPrime = false
is not prime num 33, isPrime = false
is not prime num 36, isPrime = false
is not prime num 39, isPrime = false
is not prime num 42, isPrime = false
is not prime num 45, isPrime = false
is not prime num 48, isPrime = false
is not prime num 51, isPrime = false
is not prime num 54, isPrime = false
is not prime num 57, isPrime = false
is not prime num 60, isPrime = false
is not prime num 63, isPrime = false
is not prime num 66, isPrime = false
is not prime num 69, isPrime = false
is not prime num 72, isPrime = false
is not prime num 75, isPrime = false
is not prime num 78, isPrime = false
is not prime num 81, isPrime = false
is not prime num 84, isPrime = false
is not prime num 87, isPrime = false
is not prime num 90, isPrime = false
is not prime num 93, isPrime = false
is not prime num 96, isPrime = false
is not prime num 99, isPrime = false

--> num 4, isPrime = false

--> num 5, isPrime = true
is not prime num 10, isPrime = false
is not prime num 15, isPrime = false
is not prime num 20, isPrime = false
is not prime num 25, isPrime = false
is not prime num 30, isPrime = false
is not prime num 35, isPrime = false
is not prime num 40, isPrime = false
is not prime num 45, isPrime = false
is not prime num 50, isPrime = false
is not prime num 55, isPrime = false
is not prime num 60, isPrime = false
is not prime num 65, isPrime = false
is not prime num 70, isPrime = false
is not prime num 75, isPrime = false
is not prime num 80, isPrime = false
is not prime num 85, isPrime = false
is not prime num 90, isPrime = false
is not prime num 95, isPrime = false
is not prime num 100, isPrime = false

--> num 6, isPrime = false

--> num 7, isPrime = true
is not prime num 14, isPrime = false
is not prime num 21, isPrime = false
is not prime num 28, isPrime = false
is not prime num 35, isPrime = false
is not prime num 42, isPrime = false
is not prime num 49, isPrime = false
is not prime num 56, isPrime = false
is not prime num 63, isPrime = false
is not prime num 70, isPrime = false
is not prime num 77, isPrime = false
is not prime num 84, isPrime = false
is not prime num 91, isPrime = false
is not prime num 98, isPrime = false

--> num 8, isPrime = false

--> num 9, isPrime = false

--> num 10, isPrime = false

--> num 11, isPrime = true
is not prime num 22, isPrime = false
is not prime num 33, isPrime = false
is not prime num 44, isPrime = false
is not prime num 55, isPrime = false
is not prime num 66, isPrime = false
is not prime num 77, isPrime = false
is not prime num 88, isPrime = false
is not prime num 99, isPrime = false

--> num 12, isPrime = false

--> num 13, isPrime = true
is not prime num 26, isPrime = false
is not prime num 39, isPrime = false
is not prime num 52, isPrime = false
is not prime num 65, isPrime = false
is not prime num 78, isPrime = false
is not prime num 91, isPrime = false

--> num 14, isPrime = false

--> num 15, isPrime = false

--> num 16, isPrime = false

--> num 17, isPrime = true
is not prime num 34, isPrime = false
is not prime num 51, isPrime = false
is not prime num 68, isPrime = false
is not prime num 85, isPrime = false

--> num 18, isPrime = false

--> num 19, isPrime = true
is not prime num 38, isPrime = false
is not prime num 57, isPrime = false
is not prime num 76, isPrime = false
is not prime num 95, isPrime = false

--> num 20, isPrime = false

--> num 21, isPrime = false

--> num 22, isPrime = false

--> num 23, isPrime = true
is not prime num 46, isPrime = false
is not prime num 69, isPrime = false
is not prime num 92, isPrime = false

--> num 24, isPrime = false

--> num 25, isPrime = false

--> num 26, isPrime = false

--> num 27, isPrime = false

--> num 28, isPrime = false

--> num 29, isPrime = true
is not prime num 58, isPrime = false
is not prime num 87, isPrime = false

--> num 30, isPrime = false

--> num 31, isPrime = true
is not prime num 62, isPrime = false
is not prime num 93, isPrime = false

--> num 32, isPrime = false

--> num 33, isPrime = false

--> num 34, isPrime = false

--> num 35, isPrime = false

--> num 36, isPrime = false

--> num 37, isPrime = true
is not prime num 74, isPrime = false

--> num 38, isPrime = false

--> num 39, isPrime = false

--> num 40, isPrime = false

--> num 41, isPrime = true
is not prime num 82, isPrime = false

--> num 42, isPrime = false

--> num 43, isPrime = true
is not prime num 86, isPrime = false

--> num 44, isPrime = false

--> num 45, isPrime = false

--> num 46, isPrime = false

--> num 47, isPrime = true
is not prime num 94, isPrime = false

--> num 48, isPrime = false

--> num 49, isPrime = false

--> num 50, isPrime = false

--> num 51, isPrime = false

--> num 52, isPrime = false

--> num 53, isPrime = true

--> num 54, isPrime = false

--> num 55, isPrime = false

--> num 56, isPrime = false

--> num 57, isPrime = false

--> num 58, isPrime = false

--> num 59, isPrime = true

--> num 60, isPrime = false

--> num 61, isPrime = true

--> num 62, isPrime = false

--> num 63, isPrime = false

--> num 64, isPrime = false

--> num 65, isPrime = false

--> num 66, isPrime = false

--> num 67, isPrime = true

--> num 68, isPrime = false

--> num 69, isPrime = false

--> num 70, isPrime = false

--> num 71, isPrime = true

--> num 72, isPrime = false

--> num 73, isPrime = true

--> num 74, isPrime = false

--> num 75, isPrime = false

--> num 76, isPrime = false

--> num 77, isPrime = false

--> num 78, isPrime = false

--> num 79, isPrime = true

--> num 80, isPrime = false

--> num 81, isPrime = false

--> num 82, isPrime = false

--> num 83, isPrime = true

--> num 84, isPrime = false

--> num 85, isPrime = false

--> num 86, isPrime = false

--> num 87, isPrime = false

--> num 88, isPrime = false

--> num 89, isPrime = true

--> num 90, isPrime = false

--> num 91, isPrime = false

--> num 92, isPrime = false

--> num 93, isPrime = false

--> num 94, isPrime = false

--> num 95, isPrime = false

--> num 96, isPrime = false

--> num 97, isPrime = true

--> num 98, isPrime = false

--> num 99, isPrime = false

--> num 100, isPrime = false


--> result is prime count = 25

'Algorism' 카테고리의 다른 글

알고리즘 - 프로그래머스 문자열을 정수로 바꾸기 (Swift) (0)	2020.07.02
알고리즘 - 프로그래머스 약수의 합 (Swift) (0)	2020.07.02
알고리즘 - 프로그래머스 문자열 다루기 기본 (Swift) (0)	2020.07.01
알고리즘 - 프로그래머스 문자열 내 p와 y의 개수 (Swift) (0)	2020.06.30
알고리즘 - 프로그래머스 두 정수 사이의 합 (Swift) (0)	2020.06.30

CodingLearn

CodingLearn

태그

최근글

댓글

공지사항

아카이브

'Algorism' 카테고리의 다른 글

관련글

티스토리툴바