MIDAS Challenge 2017 예선문제

문제1.

---

- 2부터 N까지의 숫자 중에서 소인수의 최댓값이 M이하인 숫자의 갯수를 구하세요.

- N의 범위가 매우 작았던 것 같다.

 

#include <iostream>
using namespace std;

int n, m, ans;

int getMax(int n) {
	int maxVar = 0;
	for (int i = 2; i <= n; ++i) {
		while(n % i == 0){
			n /= i;
			if (maxVar < i) maxVar = i;
		}
	}
	return maxVar;
}

int main() {
	cin >> n >> m;
	for (int i = 2; i <= n; ++i) {
		if (getMax(i) <= m) ++ans;
	}
	cout << ans << '\n';
	return 0;
}

 

 

 

문제2.

---

- N <= X <= M인 모든 소수 X의 합을 구하세요.  (M <= 20만)

- 범위가 큰 소수 >> 에라토스테네스의 체

 

- 이 문제를 대신 풀어도 될 것 같다.

2581번: 소수

#include <iostream>
#define MAX 10001
using namespace std;

int n, m;
long long ans;
int isNotPrime[MAX];

void getPrime(int n, int m) {
	long long sum = 0;
	isNotPrime[1] = 1;

	for (int i = 2; i <= m; ++i) {
		for (int j = i + i; j <= m; j += i) {
			isNotPrime[j] = 1;  
		}
	}
	bool find = false;
	int minPrime;
	for (int i = n; i <= m; ++i) {
		if (isNotPrime[i] == 0) {
			if(!find) minPrime = i, find = true;
			sum += i;
		}
	}
	if (sum == 0) cout << -1 << '\n';
	else cout << sum << '\n' << minPrime << '\n';
	return;
}

int main() {
	cin >> n >> m;
	getPrime(n, m);
	return 0;
}
 

 

 

 

 

문제3. 

---

- 해당 문제 대신, 백준 N과M 문제를 다풀어보면 될 것 같다.

문제집: N과 M (baekjoon)