[Swift] 알고리즘 약수,소수 공식들

1. 최대 공약수

let NM = readLine()!.split(separator: " ").map{ Int($0)! }
      
var small = min(NM[0], NM[1])
var large = max(NM[0], NM[1])

var j = 0
while(small != 0) {
	j = large % small
    large = small
    small = j
}

large // 최대 공약수

 

2. 최소 공배수

두 수의 곱을 최대 공약수로 나누면 된다!

(large * small) / gcd(large, small) // 최대 공약수 함수

 

3. 소수 구하기

해당 수가 소수인지 아닌지 판별하는 방법은 2부터 제곱근+1 까지의 수를 나누어서 확인

var num = Int(readLine()!)!

for i in Int(sqrt(Double(num))+1){
	if num % i == 0 {
    	num is not Prime
    }
}

 

4. 약수의  누적 합

N / i * i

var sum = 0
    for i in 1...N {
        sum += N / i * i
    }

 

N이 4라고 했을때

[1] [1,2] [1,3] [1,2,4] -> 1, 3, 4, 7 총 15가 나와야한다.

4, 4, 3, 4

그냥 외우도록..!

 

5. 에라토스테네스의 체 소수 목록 만들기

func sieveOfEratosthenes(limit: Int) -> [Bool] {
    var isPrime = [Bool](repeating: true, count: limit + 1)
    isPrime[0] = false
    isPrime[1] = false
    
    for i in 2...Int(sqrt(Double(limit))) {
        if isPrime[i] {
            for j in stride(from: i * i, to: limit + 1, by: i) {
                isPrime[j] = false
            }
        }
    }
    return isPrime
}

let primes = sieveOfEratosthenes(limit: MAX)

 

stride는 from부터 to 이전까지 i 만큼 수를 늘려가는 고차함수다.

이렇게 소수 배열을 만들어두고 소수인지 확인했을때 반복문이 아니라 배열의 Bool 값을 확인해서 답하면 빠르게 해결된다.

 

6. 약수의 합 배열 만들기

dp방식을 활용해서 만들어야한다.

// 약수의 합 배열
var dp = [Int](repeating:1, count:1000001)

for i in 2...1000000{
	
    var j = 1
    while i*j <= 1000000 {
    	dp[i*j] += i
        j += 1
    }
   
}

// 약수의 누적 합 배열
var s = [Int](repeating:1, count:1000001)
for i in 2...1000000 {
	s[i] = s[i-1] + dp[i]
}