📌 소수 개수 구하기 
실제 1에서 100만 까지의 소수의 개수를 나타내는 표이다.
다음 사진과 같이 2 ~ 입력받은 수 사이에 존재하는 소수의 개수를 구해보는 프로그램을 작성해보려고 한다.
어떻게 해야할까 ? 🤔
소수란 ? 1과 자기 자신을 제외한 수로 나눠지지 않는 성질이 있다.
특정 수 N이 소수인지 판별하는 방법으로는 다음과 같이 3가지가 있다.
-
2 ~ N-1의 수로 나눠보는 법. ( 나눠지면 소수가 아니다. ) -
2 ~ N/2까지만 확인하는 방법Why ? 자기자신을 제외하고 절반을 초과하는 숫자에서 나눴을때 나머지가 0이되는 숫자는 나올수가 없다.
-
2 ~ √N까지 확인하는 방법Why ? 약수의 중심을 활용하는 방법이다.
예를 들어
N이80이라고 가정하였을 때, N의 약수는 다음과 같다.1, 2, 4, 8, 10, 20, 40, 80
곱해서 80이 되는 약수의 쌍을 찾으면, 1:80, 2:40, 4:20, 8:10 이다.
여기에서 √80 = 8.xxx를 의미하고, √N은 약수의 중간 값을 의미하게 된다.
약수의 중간 값까지만 찾게 되면, 더 이상 높은 수는 찾아볼 필요가 없게 된다.
왜냐하면 중간 값인 √N 또한 N의 약수와 쌍을 이루기 때문이다. 이미 나눠지는 수를 모두 찾은 셈이 된다.
어떤게 효율적인가 ? 🤔
2 ~ N-1의 수를 모두 찾아보는 것은N-2의 연산 횟수즉 시간 복잡도는 O(N)이 된다.2 ~ N/2의 수를 모두 찾아보는 것은약 N/2의 연산 횟수시간 복잡도는 O(N)이 된다.2 ~ √N의 수를 찾아보는 것은약 √N -1시간 복잡도는 O(√N)이 된다.
2 ~ √N까지 확인하는O(√N)의 성능이 가장 좋다.
코드
import java.util.Scanner
import kotlin.math.sqrt
// 소수 찾는 알고리즘
/*
1. 2부터 판별하는 수 전까지 나눠보고 나머지가 0이 안나온다면 소수로 정의
2. 해당숫자의 절반까지만 확인하는 방법
=> 자기자신을 제외하고 절반을 초과하는 숫자에서 나눴을때 나머지가 0이되는 숫자는 나올수가 없다.
3. 해당 숫자의 √N 까지 확인하는 방법
*/
fun main() {
println("1 ~ upTo 까지의 소수 개수를 구하는 프로그램")
print("upTo ? > ")
val upTo = Scanner(System.`in`).nextInt()
val primeCount = getPrimeCount( upTo )
println("1 ~ $upTo 사이의 소수 개수는 $primeCount 개 입니다.")
}
/**
* 1 ~ upTo 범위에 소수가 몇 개인지 구하는 함수
*/
private fun getPrimeCount(upTo: Int): Int {
var primeCount = 0
var i = 2 // 1은 소수가 아니므로 2부터 확인해보자
// 2 ~ upTo 까지의 수가 소수인지 판별해보자.
while( i <= upTo ) {
if( isPrime(i) ) primeCount++
i++
}
return primeCount
}
/**
* 해당 숫자 N이 소수인지 판별하는 함수
*/
private fun isPrime( N : Int ) : Boolean {
// 1. 해당 숫자와 1을 제외하고 나눠지는지 확인하는 방법
/*
for( i in 2 until N ) {
if( N % i == 0 ) return false
}
return true
*/
// 2. 해당 숫자의 절반까지만 확인하는 방법
/*
for( i in 2..N/2 ) {
if( N % i == 0 ) return false
}
return true
*/
// 3. 해당 숫자의 √N 까지 확인하는 방법
val sqrt = sqrt(N.toDouble()).toInt()
for( i in 2..sqrt ) {
if( N % i == 0 ) return false
}
return true
}
소수 판별 알고리즘 - 에라토스테네스의 체
소수 판별 알고리즘은 위와 같은 방법을 사용하지 않고
에라토스테네스의 체알고리즘을 사용하는 것이 가장 효율적이다.
에라토스테네스의 체 알고리즘의 원리
-
판별할 범위 만큼의 크기의 배열을 생성한다.
-
2부터 시작해서 특정 숫자의 배수에 해당하는 숫자들을 지운다. 자기 자신은 지우지 않는다.
ex) 2를 제외한 2의 배수들을 모두 지운다... 모두 지웠다면 3을 제외한 3의 배수를 모두 지운다.
이 과정을 더 이상 숫자를 지울 수 없을 때까지 반복한다. -
이미 지워진 숫자의 경우 건너뛴다.
-
모든 반복을 마친 후, 2부터 시작해서 남은 수들이 판별 범위 내의 소수가 된다.
코드
import java.util.Scanner
import kotlin.math.sqrt
fun main() {
println("1 ~ upTo 까지의 소수 개수를 구하는 프로그램")
print("upTo ? > ")
val upTo = Scanner(System.`in`).nextInt()
val primeCount = getPrimeCount( upTo )
println("1 ~ $upTo 사이의 소수 개수는 $primeCount 개 입니다.")
}
/**
* 1 ~ upTo 범위에 소수가 몇 개인지 구하는 함수
*/
private fun getPrimeCount(upTo: Int): Int {
var primeCount = 0
var prime = BooleanArray( upTo + 1 ) {true}
// 에라토스테네스의 체를 활용해보자.
val sqrt = sqrt( upTo.toDouble() ).toInt() // 입력받은 수 `upTo`의 √값을 sqrt에 할당.
for ( i in 2..sqrt ) {
if( ! prime[i] ) continue // 이미 지워진 숫자의 경우 건너뛴다.
else {
var j = 2 // 2부터 시작해서 특정 숫자 i의 배수에 해당하는 숫자들을 지운다.
while ( i * j <= upTo ) { // j의 값이 2,3,4... 올라가면서 i*2, i*3, i*4 ... i의 배수들을 모두 지워가는 과정.
if( prime[i * j] ) prime[i * j] = false // true 인 값들을 false로 바꾸면서 소수 후보에서 지운다.
j++
}
}
}
// 2 ~ upTo 까지
for ( i in 2..upTo ) {
if( prime[i] ) primeCount++ // prime[i] 값이 true 이면, i 값이 소수라는 뜻이다.
}
return primeCount
}📌 참조
