*혼자 정리하기 위해 쓰는 글이라 가독성 주의
직전 문제를 풀었다면 별 다른 어려움 없이 풀 수 있는 문제였다.
다만 for loop을 어디까지 돌게할지에 따라 실행속도에서 차이가 난다.
메모리 1112KB, 20MS
짝수, 홀수 할 것 없이 2부터 m-1까지 루프를 돈다.
#include <stdio.h>
int main(void)
{
int m, n, sum = 0, i, min;
for (scanf("%d %d", &m, &n); m < n+1; m++)
{
for (i = 2; i < m && (m % i); i++);
if (i == m)
{
sum += m;
if (sum == m) min = m;
}
}
sum ? printf("%d\n%d", sum, min) : printf("-1");
return 0;
}
메모리 1112KB, 8MS
속도를 조금이라도 높이려면 어떻게 해야할까 싶어 2를 제외한 짝수는 모두 패스하게 했다.
#include <stdio.h>
int main(void)
{
int m, n, sum = 0, i, min, isPrime;
for (scanf("%d %d", &m, &n); m < n+1; m++)
{
if (isPrime = m > 1 && (m % 2 || m == 2))
{
for (i = 3; i < m && (isPrime = m % i); i += 2);
if (isPrime)
{
sum += m;
if (sum == m) min = m;
}
}
}
sum ? printf("%d\n%d", sum, min) : printf("-1");
return 0;
}
메모리 1112KB, 0MS
다른 사람 코드를 참고했다.
홀수만을 돌되 3부터 m-1까지 조건을 걸지 않고,
i * i <= m && (isPrime = m % i)
m의 제곱근까지만 돌게 한다.
왜 하필 제곱근까지일까?
소수인지 아닌지를 판가름하는 기준은 현재 탐색하는 수 m을 m-1까지의 홀수로 나누었을 때 나머지가 존재하는지 아닌지이다.
m % n = 0이 되면 m % (m / n) = 0도 성립한다.
곱이 100이 되는 자연수의 조합을 살펴보면
(1, 100) (2, 50) (4, 25) (5, 20) (10,10) (20, 5) (25,4) (50, 2) (100,1)
100의 제곱근 10의 쌍을 기준으로 순서만 다르고 숫자는 같은 조합이 두 차례씩 등장한다.
100을 만드는 자연수와 분수의 조합들까지 살펴보면
(3, 33...) (6, 16...) (7, 14...) (8, 12...) (9, 11...) (11, 9...) (12, 8...) (13, 7...) (14, 7...)
(10,10)을 기준으로 두 수의 증감 추세가 뒤바뀌는 걸 확인할 수 있다.
달리 말하면 순서가 상관없는 단순 조합의 경우 제곱근까지 확인해
자연수의 조합을 찾을 수 없다면 제곱근 이상의 수를 확인할 것도 없이 다른 자연수의 조합은 없다.
#include <stdio.h>
int main(void)
{
int m, n, sum = 0, i, min, isPrime;
for (scanf("%d %d", &m, &n); m < n+1; m++)
{
if (isPrime = m > 1 && (m % 2 || m == 2))
{
for (i = 3; i * i <= m && (isPrime = m % i); i += 2);
if (isPrime)
{
sum += m;
if (sum == m) min = m;
}
}
}
printf(sum ? "%d\n%d" : "-1", sum, min);
return 0;
}
'문제풀이' 카테고리의 다른 글
[C언어] 백준 1929번 소수구하기 (0) | 2022.01.04 |
---|---|
[C언어] 백준 11653번 소인수분해 (0) | 2022.01.04 |
[C언어] 백준 1978 소수찾기 (0) | 2022.01.03 |
[C언어] 백준 1011번 Fly me to the Alpha Centauri (0) | 2021.12.31 |
[C언어] 백준 10757 큰수 A+B (0) | 2021.12.29 |