글 읽기 - sqrt(n)사용, 리스트 사용X, c++

lucete171 3년 전 0

리스트는 사용하지 않았고 sqrt개념은 사용했는데 20%까지 가다가 시간초과 뜨네요

예제 적용이랑 2~5까지는 시험해봤는데 문제 없었습니다

혹시 리스트를 무조건 사용해야 시간초과가 안 뜬다면 그 이유 간단히 설명해주시거나 링크 걸어주실 수 있는 분 계신가요ㅜㅜ

아니면 다른 곳에 문제가 있는 걸 까요?

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

int test(int a){
	int cnt=0;
	for(int i=(a+1);i<=(2*a);i++)
	{
		int check=0;
		for(int j=2;(j*j)<=i;j++)//제곱이 i까지(sqrt(i)까지)
		{
			if(i%j==0)
			{
				check++;
			}
		}
		if(check==0)
		{
			cnt++;
		}
	}
	return cnt;
}

int main()
{
	while(1)
	{
		int n;
		scanf("%d",&n);
		if(n==0)//0일때 break
		{
			break;
		}
		else
		{
			printf("%d\n",test(n));
		}		
	}	
	return 0;
}

rnjstpgns91 3년 전 0

저도 같은 로직으로 풀었습니다. 시간초과의 이유는 소수가 아니라고 판명났음에도 모든 탐색을 하셔서 그런 것 같습니다.

lucete171 3년 전 0

소수가 아니라고 판명났음이 무슨 말인지 여쭤봐도 될까요? 모든 탐색이라는 부분도 이해가 잘 안가네요ㅜ

rnjstpgns91 3년 전 1

1. 11 ~ 19 라인의 로직이 어떤 의도일까요? (특히 11번째 줄)

2. 제가 한 모든 탐색이란 말의 의미는 9번째 for문이 전부 도는 것을 말합니다.

lucete171 3년 전 0

11번쨰 if 문에 break 걸어줬더니 풀렸네요 감사합니다ㅋㅋ

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

문제

문제

출처

ICPC

sqrt(n)사용, 리스트 사용X, c++

lucete171 3년 전 0

rnjstpgns91 3년 전 0

lucete171 3년 전 0

rnjstpgns91 3년 전 1

lucete171 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말