Baekjoon 17173 배수들의 합

Link https://www.acmicpc.net/problem/17173

소스결과 1988KB / 0 ms

언어 C++ 17

출처 Baekjoon

분류 수학, 에라토스테네스의 체

 

설명

자연수 K개 각각의 배수 중 N 이하의 합을 구하여라. 단 중복은 한번만 더한다.

 

에라토스테네스의 체와 유사한 방식으로 해결한다.

 

소스코드

#include <iostream>

using namespace std;

const int MAX = 1000;

bool checkBoard[MAX + 1];

int main()
{
	int n, m; cin >> n >> m;

	int start = -1;

	while (m--) {
		int k; cin >> k;

		if (start == -1)
			start = k;

		for (int i = 1; i * k <= 1000; i++)
			checkBoard[i*k] = true;
	}

	int sum = 0;
	for (int i = start; i <= n; i++)
		if (checkBoard[i])
			sum += i;

	cout << sum;

	return 0;
}