Swift. 소수 찾기

 문제.

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

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

제한 조건

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

import UIKit
func solution1(_ n: Int) -> Int {
    var result = 0
    var array = Array.init(repeating: false, count: n+1)
    
    for i in 2...n {
        if (!array[i]){
            result += 1
            for j in stride(from: i, through: n, by: i) {
               array[j] = true
            }
        }
    }
    return result
}

요구사항. 

• 오랜만에 머리좀 썻네요 ㅎㅎ;;;
• 먼저 주어지는 숫자만큼의 배열을 false로 지정해준다.
• 알고리즘 방식을 이용하려면 2~n까지의 숫자인 i가 들어가서 자기 자신을 제외한 배수는 모두 약수의 조건에 해당할수 없기때문에 stride를 사용해서 배수에 해당하는 숫자들을 모두 지워준다.
• 이렇게 진행하면 2가 들어가서 카운트 1이되고 2의 배수를 모두 true로 바꾸고
• 3이들어가서 카운트가 2가되고 3의 배수를 모두 true로 바꾸고
• 4는 처음에 2가 진행될때 false가 true로 바뀌어서 조건문에 안맞아서 바로 5가 실행된다.
• 이렇게 모든수가 실행되면 나중에는 약수의 개수만큼 result가 남게된다.
• 만약 소수들의 모음을 구하고 싶다면 어떻게 해야할까? 
  • 숫자를 카운트하고 다음 반복문이 들어가기전에 i를 다른배열에 append해주면 된다.