[BOJ]2581号小数

𕼧問題の説明

コア原理

💻コード#コード#

最初の問題を解く

#include <iostream>
#include <vector>
using namespace std;

int main(void) {
	ios::sync_with_stdio(0); // C 표준 stream과 C++ 표준 stream의 동기화를 끊는다.
	cin.tie(0);

	int M, N;
	int min = 0;
	int sum = 0;
	vector<int> s; // 소수만 담겨있다.

	cin >> M >> N;

	s.push_back(2); // 2가 소수임을 알고 있는 가정 하에 

	for (int i = 3; i < M; i++) {
		// M 전까지 소수 담기 
		int j = 0; 
		for (; j < s.size(); j++) {
			if (i % s[j] == 0) break; // 소수 중 하나라도 나줘지면 기각
		}
		if (j == s.size()) s.push_back(i); // 소수 추가 
	}

	for (int i = M; i < N + 1; i++) {
		int j = 0;
		for (; j < s.size(); j++) {
			if (i % s[j] == 0) break; // 소수 중 하나라도 나줘지면 기각
		}
		if (j == s.size()) {
			s.push_back(i);
			if (sum == 0) min = i; // 최솟값 
			sum += i; // 합을 더해줌 
		}
	}

	if (sum == 0) {
		cout << -1;
	}
	else {
		cout << sum << "\n" << min;
	}
}

第一次危機:反例2,2出力-1なのでNが2の場合出力2後に終了

第2題を解く

#include <iostream>
#include <vector>
using namespace std;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int M, N = 0;
	int min = 0;
	int sum = 0;

	cin >> M >> N;

	vector<int> s; // 소수가 담겨있다. 
	s.push_back(2);

	for (int i = 1; i < N + 1; i++) {
		int j = 0;
		for (; j < s.size(); j++) {
			if (i % s[j] == 0 || i ==1) { // 1은 기각 
				if (i == 2) { // 나눠지는 수 중 2는 계속 진행시켜서 j++를 수행시킨다. 
					continue;
				}
				break;
			}
		}
		
		if (j == s.size()) {
			s.push_back(i);
			if (i >= M) { // i가 M보다 클 때 더함
				if (sum == 0) {
					min = i;
				}
				sum += i;
			}
		}
	}

	if (sum == 0) {
		cout << -1;
	}
	else {
		cout << sum << "\n" << min;
	}
}

#include <iostream>
using namespace std;

int main()
{
	int max, min;
	int count = 0; // 나눠떨어지는 수의 갯수
	int nCount = 0;  // 소수 갯수
	int result = 0, minNumber;  // 합, 소수 최솟값

	cin >> min;
	cin >> max;

	for (int i = min; i <= max; i++) // min부터 max에 대해서 
	{
		for (int j = 1; j <= i; j++) // 1부터 자기자신까지 나눈다.
		{
			if (i % j == 0)
				count++;
		}

		if (count == 2) / /소수인경우
		{
			nCount++; // 소수 개수 count
			result += i; // 더함

			if (nCount == 1) // 최쵤때 
				minNumber = i;
		}
		count = 0;
	}

	if (nCount == 0)
	{
		minNumber = -1;
		cout << minNumber << endl;
	}
	else
	{
		cout << result << endl << minNumber << endl;
	}
		
	return 0;
}

、すなわちMからNをiで割る(i=1~i=k[k=M,M+1,M+2,,,,,,,,,,,N])

確かに、小数を格納した後、小数を利用して小数を検索する戦略はもっと速いです.