글 읽기 - 에라토스테네스의 체를 이용했는데 너무 느린것 같습니다.

zxcv551133 6년 전 0

getPrimeset() 함수로 에라토스테네스의 체를 전처리 하는데 10000000을 넣을 경우 너무 느린 속도가 나옵니다.

어디에서 잘못한건지 궁금합니다.

// 미해결
// https://www.acmicpc.net/problem/1456
// 거의 소수
#ifndef ONLINE_JUDGE
#define _CRT_SECURE_NO_WARNINGS
#endif // !ONLINE_JUDGE
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <algorithm>
#include <math.h>
#include <bitset>
#include <set>
#include <map>
#include <queue>
#include <functional> //greater less
using namespace std;
const int I32MAX = 2147483647;

vector<long long> primeSet(1000000);

//minVal 이상, maxVal 이하의 소수들의 개수를 return 찾는다.
long long go(long long minVal, long long maxVal, double p) {
	long long minInt = pow(minVal, 1 / p);
	long long maxInt = pow(maxVal, 1 / p);
	if (minInt != pow(minVal, 1 / p)) minInt++;
	return upper_bound(primeSet.begin(), primeSet.end(), maxInt)
		- lower_bound(primeSet.begin(), primeSet.end(), minInt);
}
//val 이하의 소수들을 구해 primeSet에 집어넣음
void getPrimeSet(int val) {
	vector<bool> ar(val + 1);
	ar[0] = 1; ar[1] = 1;
	int cnt = 1; primeSet[0] = 2;
	for (int i = 3; i*i <= val; i += 2) {
		if (ar[i] == 0) {
			for (int j = i*i; j <= val; j += i * 2) {
				ar[j] = 1;
			}
		}
	}
	for (int i = 3; i <= val; i+=2) {
		if (ar[i] == 0) {
			primeSet[cnt++] = i;
		}
	}
	primeSet.resize(cnt);
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif // !ONLINE_JUDGE
	cin.tie(0); ios_base::sync_with_stdio(0);

	//write your code here

	long long a, b;
	cin >> a >> b;

	getPrimeSet(10000000);
	long long count = 2;
	long long ans = 0;
	for (long long i = 1; i < b; i *= 2) {
		ans += go(a, b, count++);
//		cout << count << ' ' << ans << '\n';
	}
	cout << ans << '\n';

	// code ended
	return 0;
}

jwvg0425 6년 전 0

제 컴퓨터에서 실행해보니 에라토스테네스의 체는 빠르게 잘 도는 거 같은데요??

zxcv551133 6년 전 0

제 환경에서 8초이상 걸리더라구요..
그렇다면 WA 이유는 뭘까요..

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

문제

문제

출처

ICPC

에라토스테네스의 체를 이용했는데 너무 느린것 같습니다.

zxcv551133 6년 전 0

jwvg0425 6년 전 0

zxcv551133 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말