글 읽기 - 풀기는 했는데 더 나은 방법이 있는지 궁금해요

jormal 7년 전 0

sqrt(max)보다 작은 소수 들의 제곱들을 구해서

min 부터 max까지 나눠지는 수들을 체로 거르는 방법으로 답을 구했어요

뭔가 껄쩍지근한 느낌인데.. 무식한거같기도 하구요

좀 더 나은 방법은 없을까요?

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

using namespace std;

bool prime[2000000] = {false};
bool square[2000000] = {false};
vector < unsigned long long int > p;
int p_size = 0;	int s_size = 0;

int main() {
	unsigned long long int min, max;
	unsigned long long int temp, t_min, t_max;

	scanf("%llu %llu", &min, &max);
	temp = sqrtl((long double)max);

	prime[0] = prime[1] = true;
	for(unsigned long long int i=2;i<=temp;i++) {
		if(prime[i]) continue;
		for(unsigned long long int j=i*2;j<=temp;j+=i) {
			if(prime[j]) continue;
			prime[j] = true;
		}
		p.push_back(i*i);
		p_size++;
	}

	for(unsigned long long int i=0;i<p_size;i++) {
		if(min % p[i]) {
			t_min = ((unsigned long long int)(min / p[i]) + 1) * p[i];
		}
		else {
			t_min = min;
		}

		t_max = (unsigned long long int)(max / p[i]) * p[i];

		for(unsigned long long int j=t_min;j<=t_max;j+=p[i]) {
			if(square[j-min]) continue;
			square[j-min] = true;
		}
	}

	for(int i=0;i<=max-min;i++) {
		if(!square[i]) s_size++;
	}

	printf("%d", s_size);
	return 0;
}

sgchoi5 7년 전 1

문제를 풀면 다른 분들의 코드를 보실 수 있으니, 참고하시면 될 듯 합니다.

jormal 7년 전 0

오랜만이라 깜빡했네요... 감사합니다

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

문제

문제

출처

ICPC

풀기는 했는데 더 나은 방법이 있는지 궁금해요

jormal 7년 전 0

sgchoi5 7년 전 1

jormal 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말