소수 찾기 (Lv1. Swift)

소수 찾기 (Lv1. Swift)

🔍 문제

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

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

🔶 제한사항

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

🔹 입출력 예

🔹 입출력 예 설명

입출력 예 #1 1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2 1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

---

📌 풀이

소수를 다시 표현해보면 1과 자기자신을 제외한 약수가 없는 수이다.

2는 1과 2외에 약수가 존재하지 않는다. 그러므로 소수이다.

9의 약수는 1, 3, 9로 1과 자기자신외에도 3이라는 약수가 존재하므로 소수가 아니다.

따라서 9가 소수인지 알고 싶다면 2부터 9까지의 숫자 중 나누어 떨어지는 수(여기서는 3)가 있는지 체크해 보고, 있다면 소수가 아니라고 판단하면 된다.

이때 2부터 9까지 모두 검사 할 필요는 없고 9의 루트 값인 3까지만 검사를 해보면 된다.

예를 들어 95가 소수인지 확인해 보도록 하자.

95의 약수는 1, 5, 19, 95이다. 이때 5까지만 확인하면 해당 수는 소수가 아니라는 것을 확인 할 수 있고 19까지 나눠 볼 필요가 없게 된다.

루트값 이후의 값으로 나누어 떨어지려면(이 경우 19) 반드시 해당 수의 몫이 루트값(약9.75) 이하에 존재(여기선 5가 있다)해야 한다.

다른 수를 예로 들어 보자.

121의 약수는 1, 11, 121이다.

이 경우 11은 루트121에 해당한다. 1과 자기 자신을 제외한 약수가 존재할 수 있는 수 중 최대값이 바로 해당 수의 루트값이다.

따라서 루트값까지만 확인해 보면 된다!

1. 먼저 2부터 입력받은 숫자까지의 반복문을 구현하고,

2. 그 안에 2부터 입력 받은 숫자의 루트까지 반복하여 해당 수가 나누어 떨어지는 지 확인하는 반복문을 구현한다.

3. 만약 나누어 떨어진다면 해당 수는 소수가 아니라고 판별 하고 그 즉시 반복문 탈출(break)!

   -> 여기서 소수는 자기 자신을 제외하고 나누어 떨어지는 수이므로 “ i != j “ 를 통해 자기 자신으로 나누어 떨어지는 경우에는 소수로 체크될 수 있도록 한다

4. 해당 수가 소수가 맞다면 count +1이 되도록 구현하고,

5. 최종적으로 count를 return하면 끝!

func solution(_ n:Int) -> Int {
var isPrime = true
var count = 0

for i in 2...n {
	isPrime = true
	for j in 2...Int((sqrt(Double(n)))) + 1 {
		if i != j && i % j == 0 {
			isPrime = false
			break
		}
	}
	count = isPrime ? count + 1 : count
}
return count
}

print(solution(5)) // 4

---

Reference

프로그래머스 - https://programmers.co.kr/learn/courses/30/lessons/12921