약수

[백준] 1037 약수 (Java)

✉️문제 https://www.acmicpc.net/problem/1037 1037번: 약수 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되 www.acmicpc.net 📝 접근 약수의 개수가 1과 자기자신을 빼고 주어진다. 따라서 주어진 약수 중에서 가장 작은 값과 가장 큰 값을 곱하면 된다. 🗝 문제풀이 package divisor; import java.util.Arrays; import java.util.Scanner; public class B1037R { public static void main(String[] args) { Scann..

[백준] 17427 약수의 합2 (Java)

✉️문제 https://www.acmicpc.net/problem/17427 17427번: 약수의 합 2 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net 📝 접근 https://brightmango.tistory.com/345 [알고리즘] 약수 알고리즘 A와 B라는 숫자가 있을 때 A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 이런 약수를 구하는 방법은 3가지가 있다. 모든 자연수로 나누는 방법 : O(n) 말 그래도 1부터 N까지 모든 수로 나누어 brightmango..

[알고리즘] 약수 알고리즘

A와 B라는 숫자가 있을 때 A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 이런 약수를 구하는 방법은 3가지가 있다. 모든 자연수로 나누는 방법 : O(n) 말 그래도 1부터 N까지 모든 수로 나누어 보는 방법이다. 10이라는 숫자의 약수를 알기 위해 10번의 나눗셈 연산이 필요하다. 약수가 되는 성질을 이용한 방법 : O(√n) C가 A의 약수라면, A/C도 A의 약수가 된다. 즉 1 ~ √n 까지 구하면 된다. 배수의 성질을 이용한 방법 약수인 수보다 약수가 아닌 수가 더 많이 존재한다. 따라서 배수의 성질을 이용하면 약수만 빠르게 구할 수 있다. 알고리즘 문제 풀이에서는 주로 이 알고리즘이 사용된다. 다음 그림과 함께 6을 기준으로 어떤 성질을 가지고 있는지 확인해보자. 6이하의 자연수 ..