10430
- 문제
https://www.acmicpc.net/problem/10430
(A+B)%C는 ((A%C) + (B%C))%C 와 같을까?
(A×B)%C는 ((A%C) × (B%C))%C 와 같을까?
- 풀이
주어진 식대로 System.out.println() 해주면 된다.
4375
- 문제
https://www.acmicpc.net/problem/4375
1로만 이루어진 n의 배수를 찾아, 그 중 가장 작은 수의 자리수를 출력하라.
- 풀이
input = n
num = num * 10 + 1; // 1, 11, 111, ... 1로만 이뤄진 수를 구한다.
num = num % n; // n의 배수인지 확인하기 위해 나머지를 구한다.
1037
- 문제
https://www.acmicpc.net/problem/1037
양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다.
어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오.
- 풀이
약수가 전부 주어지기 때문에 가장 작은 수 * 가장 큰 수 가 N이 된다.
17427
- 문제
https://www.acmicpc.net/problem/17427
두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다.
예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다.
자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다.
x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다.
자연수 N이 주어졌을 때, g(N)을 구해보자.
- 풀이
n 이하인 수들 중에서 i를 약수로 갖는 수
=> n 이하의 i의 배수
=> 개수를 구하려면 n/i 이다.
answer += i * (n / i)
입력이 최대 1,000,000 이므로 long 타입으로 선언해야 한다.
17425
- 문제
https://www.acmicpc.net/problem/17425
문제는 위 17427번과 같지만 입력 방법이 다르다.
- 풀이
해당 자연수의 약수의 합을 저장하는 코드: N logN
이전 약수의 합을 저장하는 코드(dp): N
테스트 케이스 만큼 실행되는 코드: T
총 시간 복잡도는 N logN + T 이므로 위 계획으로 문제를 풀 시간은 충분하다.
그러나 테스트 케이스마다 약수의 합을 구하는 코드를 실행하면 시간 초과가 뜬다.
미리 문제를 해결해놓고 테스트 케이스에 따라 답을 꺼내와야 한다.
2609
- 문제
https://www.acmicpc.net/problem/2609
- 풀이
최소 공배수는 N * M /최대 공약수 로 구할 수 있다.
1978
- 문제
https://www.acmicpc.net/problem/1978
주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.
- 풀이
에라토스테네스의 체를 이용하여 소수를 찾는다.
2의 배수 제거, 3의 배수 제거, … 를 반복하는 개념이다.
boolean[] prime = new boolean[n + 1];
Arrays.fill(prime, true);
// 0 과 1 은 소수가 아니므로 false
prime[0] = false;
prime[1] = false;
for (int i = 2; i * i <= n; ++i) {
if (prime[i]) {
// 이미 2의 배수가 걸러졌기 때문에 i 의 제곱수부터 시작해도 된다.
for (int j = i * i; j <= n; j += i) {
prime[j] = false;
}
}
}
1929
- 문제
https://www.acmicpc.net/problem/1929
M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.
- 풀이
에라토스테네스의 체를 이용하여 소수를 찾는다.
코드는 위와 동일하다.
6588
- 문제
https://www.acmicpc.net/problem/6588
4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.
예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다.
- 풀이
이것도 에라토스테네스의 체를 이용하여 소수를 찾은 후 시작한다.
while (true) {
int num = Integer.parseInt(br.readLine());
boolean ok = false;
if (num == 0) {
break;
}
for (int i = 2; i <= num / 2; i++) {
if (prime[i] && prime[num - i]) {
sb.append(num + " = " + i + " + " + (num - i) + "\n");
ok = true;
break;
}
}
if (!ok) {
sb.append("Goldbach's conjecture is wrong.\n");
}
}