백준 1016 c++ "제곱 ㄴㄴ 수" -PlusUltraCode-

https://www.acmicpc.net/problem/1016

 

[필자 사고]

이 문제는 에스트라 채를 알고 있냐 없냐 묻는 문제이다.

그리고 중요한 점은 시작 위치를 정하는 startIdx를 구하는 방법인데

필자는 다음과 같이 구했다.

(minNum+square-1)%square*square 방식을 startIdx를 구하고

startIdx의 실제 배열의 위치를 구하기 위해

startIdx - minNum 을 하게 되면 배열 압축을 할 수 있게 된다.

이 정도만 조심하면 문제를 해결할 수 있다.

[코듷 해설]

 

• 입력 받기:
  • minNum과 maxNum 값을 입력받아 분석할 범위를 설정합니다.
• 에라토스테네스의 체 변형:
  • isPrime 벡터를 [minNum,maxNum][minNum, maxNum][minNum,maxNum] 범위 내의 숫자를 나타내는 크기로 초기화하고 모든 값을 true로 설정합니다.
  • i=2i = 2i=2부터 시작하여 i2i^2i2을 계산하고, 이 값으로 나누어떨어지는 숫자들을 false로 표시합니다.
  • 범위 내에서 i2i^2i2의 배수를 체크하기 위해 시작 인덱스를 다음과 같이 계산합니다: startIdx=입니다.
• 유효한 숫자 세기:
  • 모든 i2i^2i2에 대해 처리한 후, isPrime 벡터에서 true로 남아 있는 숫자는 완전제곱수로 나누어떨어지지 않는 숫자입니다. 이 개수를 세어 결과를 출력합니다.
  •  
• 결과 출력:
  • 범위 내에서 조건을 만족하는 숫자의 개수를 출력합니다.

 

[소스 코드]

#include <iostream>
#include <vector>
#define ll long long

using namespace std;

ll minNum, maxNum;

void Estra() {
	vector<ll> isPrime;
	ll size = maxNum - minNum + 1;
	isPrime.resize(size,true);

	for (ll i = 2; i * i <= maxNum; i++) {
		ll nowNum = i * i;
		ll startIdx = (minNum + nowNum - 1)/nowNum*nowNum;

		for (ll k = startIdx; k <= maxNum; k += nowNum) {
			isPrime[k-minNum] = false;
		}
	}

	int count = 0;
	for (ll i = 0; i < isPrime.size(); i++) {
		if (isPrime[i])count++;
	}

	cout << count;
}

void Game_Start() {
	cin >> minNum >> maxNum;

	Estra();
	
}

int main(void) {
	Game_Start();
}