글 읽기 - 1016번 제곱 ㄴㄴ 수 시간초과... 힌트좀 주세요 ㅠ

gkfkagkfka12 6년 전 0

질문들을 보면서 다음 방법들을 썼습니다.

에라토스테네스의 체를 이용해서 min~max 사이의 소수들을 구한 뒤 prime 벡터에 집어넣는다.
prime벡터에서 각 원소들을 제곱한다. 제곱수이기 때문에.
그렇게 소수의 제곱수를 뽑아내서 min~max 사이의 제곱수로 나눠지지 않는 수를 찾아서 출력한다.

어느 부분에서 시간초과가 나는 건가요..? 힌트 좀 주실 수 있나요?

#include <cstdio>
#include <cmath>
#include <vector>

typedef long long ll;
ll num[1000005];
ll temp[1000005];
std::vector<ll> prime;

void Eratos(int min, int max)
{
	for (int i = 2; i < std::sqrt(max) + 1; i++) {
		for (int j = 0; j < max - min + 1; j++) {
			if (temp[j] == -1) continue;
			if (temp[j] == 1 || (temp[j]>i && temp[j] % i == 0)) temp[j] = -1;
		}
	}
	for (int i = 0; i < max - min + 1; i++)
		if (temp[i] != -1) prime.push_back(temp[i]);
	for (int i = 0; i < prime.size(); i++) prime[i] *= prime[i];
}

int main(void)
{
	ll min, max; scanf("%lld %lld", &min, &max);
	for (int i = min, j = 0; i <= max; i++, j++) {
		num[j] = i;
		temp[j] = i;
	}
	Eratos(min, max);

	for (int i = 0; i < prime.size(); i++) {
		for (int j = 0; j < max - min + 1; j++) {
			if (num[j] % prime[i] == 0) num[j] = -1;
		}
	}

	int n = 0;
	for (int i = 0; i < max - min + 1; i++) {
		if (num[i] != -1) n++;
	}
	printf("%d", n);
	return 0;
}

atomzeno 6년 전 0

에라토스테네스의 체를 이용해서 min~max 사이의 소수들을 구한 뒤 prime 벡터에 집어넣는다.

min,max< 1000000000000....에라토스테네스 체로 모든 소수를 구하기엔 무리가?

그것보다는 min~max 사이에 p² 의 배수들에 check를 해주면서 가는게 좋겠죠. 그러면 sqrt( 1000000000000 )이하의 소수만 구하면 되니까용.k2

min<= p² k1, p² k2<=max 만족하는 k1~k2까지 for로 i를 돌려주면서 말이죠.

gkfkagkfka12 6년 전 0

p랑 k1, k2는 어디서 나온거죠??

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

문제

문제

출처

ICPC

1016번 제곱 ㄴㄴ 수 시간초과... 힌트좀 주세요 ㅠ

gkfkagkfka12 6년 전 0

atomzeno 6년 전 0

gkfkagkfka12 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말