글 읽기 - 고수님들 시간초과가 뜨는데 왜뜨는지 이해가 잘 안됩니다.ㅠㅠ

hong4243 7년 전 0

시간 초과가 나오는데 왜 나오는지를 모르겠네요ㅠㅠ

알려주시면 정말감사할것 같습니다!!

#include <stdio.h>

void check(int input);

int main()
{
	int minNumber;
	int maxNumber;

	scanf("%d %d", &minNumber, &maxNumber);

	for (int i = minNumber; i <= maxNumber; i++){
		check(i);
	}

}

void check(int input)
{
	int check = 0;

	for (int i = 2; i < input; i++){
		if (input % i == 0)
			break;
		else
			check++;
	}

	if (check == input - 2){
		printf("%d\n", input);
	}
}

jseo 7년 전 0

알고리즘이 느립니다.

에라토스테네스의 체를 써야 합니다.

wisqa 7년 전 1

에라토스테네스의 체까지는 안 해도 되고, 해당 수의 제곱근까지만 나머지를 확인해 주시면 됩니다.

void check(int input)
{
    int max = sqrt(input);
	
	if (input == 1)
		return;

	for (int i = 2; i <= max; i++)
		if (input % i == 0)
			return;

	printf("%d\n", input);
}

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

문제

문제

출처

ICPC

고수님들 시간초과가 뜨는데 왜뜨는지 이해가 잘 안됩니다.ㅠㅠ

hong4243 7년 전 0

jseo 7년 전 0

wisqa 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말