[C언어] 백준 2581번 소수

*혼자 정리하기 위해 쓰는 글이라 가독성 주의

 

직전 문제를 풀었다면 별 다른 어려움 없이 풀 수 있는 문제였다.

다만 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;
}