글 읽기 - 제 뭐같이 오래걸리는 풀이를 어떻게 하면 옳은 방향으로 이끌 수 있을까요..

icantgiveup 3년 전 0

답도 없이 길기만 한데 뭔가 어떻게 고쳐야 할 지 감도 안오고, 한번 생각을 잘못해서 인가, 다른 풀이들을 봐도 이해가 안대요,,, 도와주세요,,,

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
typedef long long ll;

bool a[1001005];


ll zmin, zmax;
vector <ll> squareprime;
vector <pair <bool, ll>> z;

void eratos(int k) {
	if (k <= 1) {
		return;
	}
	for (ll i = 2; i * i <= k; i++) {
		if (a[i]) {
			for (ll j = i * i; j <= k; j += i) {
				a[j] = 0;
			}
		}
	}
}

int main() {
	fastio;

	for (int i = 2; i <= 1001000; i++) {
		a[i] = 1;
	}

	eratos(1001000);

	for (ll i = 2; i <= 1001000; i++) {
		if (a[i]) {
			squareprime.push_back(i);
		}
	}

	cin >> zmin >> zmax;
	for (ll i = zmin; i <= zmax; i++) {
		z.push_back({ 1, i });
	}

	int total = 0;
	for (ll i = 0; i < z.size(); i++) {
		int piv = 1;
		if (z[i].first) {
			for (ll j : squareprime) {
				if (z[i].second % (j * j) == 0) {
					for (ll k = i; k < z.size(); k += j * j) {
						z[k].first = 0;
					}
					piv = 0;
					break;
				}
			}
			if (piv) {
				total++;
			}
		}
	}

	cout << total;

	return 0;
}

dayo05 2년 전 1

zmin, zmax를 입력 받은 이후의 코드를 최적화 가능할거 같습니다.

힌트를 드리자면 저는 O(sqrt(zmax)*(zmax-zmin))으로 풀었습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

제 뭐같이 오래걸리는 풀이를 어떻게 하면 옳은 방향으로 이끌 수 있을까요..

icantgiveup 3년 전 0

dayo05 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말