[프로그래머스] 소수 찾기

문제 설명

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

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

제한 조건

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

입출력 예

n	result
10	4
5	3

입출력 예 설명

입출력 예 #1

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

입출력 예 #2

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

이해

💡 기존에 javascript로 이 문제를 풀었던 기억이 있는데
kotlin 으로는 현재 제공이 되지 않아서 자체적으로 풀어봤다

에라토스테네스의_체 알고리즘 에라토스테네스의 체

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6 .남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

풀이

/**
 * You can edit, run, and share this code. 
 * play.kotlinlang.org 
 */

fun main() {
    
    var isPrimeArr = ArrayList<Int>()   
    
    var statrtNum = 2
    
    for(i in 2..120) {
        if(isPrime(i)){
            isPrimeArr.add(i)
        }
    }
    
    println(isPrimeArr)
}

// 소수 판별
fun isPrime(n : Int) : Boolean {
    
    // 1은 소수가 아니기 때문에 2부터 시작
    var i = 2
    
    while(i * i <= n ) { // 주어진 수 만큼 while문 진행
        
        if(n % i++ == 0) return false // 2부터 N-1까지의 수로 나누었을 때 나머지가 0이되면 안된다.        
    }
    
    return true
}

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113]

🤣 문돌이 출신 + 비 전공으로 진입해서 그런지 모르겠지만
알고리즘 이해를 하는 시간이 너무 오래걸린다. 하지만 드디어 이해완료!

피드백은 언제나 환영입니다. 🦾