글 읽기 - 뭐땜시 시간초과?!?!

tbfpr789 1년 전 0

안녕하세요 제가 위 문제를 잘 풀고 제출했는데 시간 초과가 뜨네요..

혹시 제가 푼 방식이 잘못됐을까요? 아니면 제가 놓친 부분이 있을까요??

감사합니다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#pragma warning(disable:4996)


int main(void)
{
	int start, done;
	int i,j;

	scanf("%d %d", &start, &done);

	if (done > 1000000)
		return 0;


	for (i = start; i < done + 1; i++)
	{

		for (j = 2; j < i; j++)
		{
			if (i % j == 0)
				break;

			else if(j == i -1)
			printf("%d\n", i);
		}

		
	}


	return 0;
}

pill27211 1년 전 1

2부터 하나하나 나눠보는 것은 (1 ≤ M ≤ N ≤ 1,000,000)와 제한 시간을 보면 절대 통과할 수 없습니다.O(N^2)

'에라토스테네스의 체'라는 것에 대해 공부해 보세요.

소수 판정에 있어서 굉장히 효율적인 알고리즘 입니다.

시간 복잡도 또한 O(NloglogN)으로 앞선 완전탐색에 비하면 더없이 빠르지요.

tbfpr789 1년 전 1

매번 감사합니다^^ 에라토스테네스에 대해서 공부해보겠습니다!!

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

문제

문제

출처

ICPC

뭐땜시 시간초과?!?!

tbfpr789 1년 전 0

pill27211 1년 전 1

tbfpr789 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말