백준 1016 : 제곱 ㄴㄴ 수

www.acmicpc.net/problem/1016

1016번: 제곱 ㄴㄴ 수

이 문제의 경우 주어지는 수가 최대 1,000,001,000,000 으로 그 값이 매우 크고 max - min 값도 최대 1,000,000 으로 커서 O(n^2)을 돌릴 수 없는 문제이다. 모든 제곱수에 대하여 확인하는 것이 아니라 제곱수로 만들 수 있는 제곱수는 배제함으로써 연산 횟수를 줄이려고 하였으나 에라토스테네스의 체 방법을 사용하여 소수를 구하는 과정에서 생기는 연산으로 인해 결과적으로는 비슷한 것 같다.

max값이 최대 1,000,001,000,000 이지만 제곱수로 나누어주므로 sieve(뜻: 체) 배열의 크기는 1,001,000까지 선언한다.

 

#include <iostream>
#include <math.h>
#include <vector>

using namespace std;

typedef long long ll;

vector<ll> prime_num;
bool check[1000001];
bool sieve[1001000];

int main() {
	ll min, max, margin, ans = 0;

	cin >> min >> max;
	fill(sieve, sieve + (int)sqrt(max) + 1, 1);
	sieve[0] = sieve[1] = 0;
	for (ll i = 2; i <= sqrt(sqrt(max)); i++) {
		if (!sieve[i]) continue;
		for (ll j = i * i; j <= sqrt(max); j += i) {
			sieve[j] = 0;
		}
	}
	for (ll i = 1; i <= sqrt(max); i++) {
		if (sieve[i]) prime_num.emplace_back(i * i);
	}

	for (int idx = 0; idx < prime_num.size(); idx++) {
		margin = min % prime_num[idx] == 0 ? prime_num[idx] : min % prime_num[idx];
		for (ll i = min + prime_num[idx] - margin; i <= max; i += prime_num[idx]) check[i - min + 1] = 1;
	}
	for (int i = 1; i <= max - min + 1; i++) {
		if (!check[i]) ans++;
	}
	cout << ans;
	return 0;
}

메모리: 5532 kb

시간: 16 ms