[오로라 프로젝트 1] 3 과 5 의 복수

나의 새 블 로그 방문 을 환영 합 니 다: http://www.milkcu.com/blog/
원문 주소: http://www.milkcu.com/blog/archives/1367311260.html
머리말
어제 Project Euler 괜 찮 은 Project 를 발 견 했 고 수학, 컴퓨터, 영어 방면 의 사고 와 능력 도 개선 했다.
매일 조금씩 하 는 것 도 옳 은 선택 이 니 오늘 은 첫 번 째 문제 부터 노력 하 자.
이 항목 은 답 을 제출 한 후에 문제 분석 을 받 을 수 있 습 니 다. 작가 의 희망 에 따라 pdf 는 공유 하지 않 습 니 다.

제목 설명
원문:
Multiples of 3 and 5
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.
중국어 표현 은 다음 과 같다.
3 과 5 의 공배수
만약 우리 가 10 이하 3 과 5 의 공배수 를 열거 한다 면, 우 리 는 3, 5, 6, 9 를 얻 을 수 있다. 이 공배수 의 합 은 23 이다. 1000 이하 3 과 5 의 공배수 의 합 을 구한다.
간단 한 방법
간단 한 사고방식 은 다음 과 같다 (C 언어 실현).

# include <stdio.h>
# define NUM 1000
int main(void)
{
	int n;
	int i;
	int sum;
	
	sum = 0;
	for(n = 1; n < NUM; n++) {
		if(n % 3 == 0 || n %5 == 0) {
			sum += n;
		}
	}
	printf("%d", sum);
}

그러나 우 리 는 수량급 이 점점 커지 는 과정 에서 더 좋 은 방법 이 필요 할 지도 모른다 는 것 을 곰 곰 이 생각해 보 자.
보다 효과 적 인 방법
우 리 는 (3 의 공배수 와 + 5 의 공배수 의 합 - 15 의 공배수 의 합) 을 계산 하고 1 + 2 + 3 +... + p = 0.5 * p * (p + 1) 의 구 화 공식 을 이용 하여 시간 복잡 도 를 더욱 줄 일 수 있다.

# include <stdio.h>
# define NUM 1000
int sumdiv(int n);
int main(void)
{
	printf("%d", sumdiv(3) + sumdiv(5) - sumdiv(15));
}
int sumdiv(int n)
{
	int i;
	
	i = (NUM - 1) / n;    //      
	return n * 0.5 * i * (1 + i);
}

시간 복잡 도 는 O (n) 에서 O (1) 로 떨어진다.
후기
이 문제 의 사고방식 은 이해 하기 어렵 지 않 지만 예전 의 나 에 게 유연 한 운용 이 부족 해서 먼저 생각 한 것 은 간단 한 방법 이다.
답 을 제출 한 후, Congratulations 를 보고 나 도 더욱 흥분 했다.

나 도 28840 분 의 1 이 야.