글 읽기 - 런타임에러!! 도와주세요!

rim0621 7년 전 0

런타임에러가 뜨는데... 왜그런걸까요... 출력은 맞는거같은데

그리고 요즘 빅오 표기법 공부중이라...

n+n+n루트n 이니까O (2+루트(n))n 맞나요??

#include<stdio.h>
#include<math.h>
int main()
{
	int m = 0, n = 0;
	scanf("%d %d", &m, &n);
	int *prime = (int*)malloc(sizeof(int)*n);
	
	if (m == 1)
	{
		m += 1;
	}

	for (int i = m; i <= n; i++)  //n
	{
		prime[i] = 0;
	}
	for (int i = 2; i < sqrt(n) ; i++) //sqrt(n)
	{
		for (int j = i * 2; j <= n; j+=i) //n
		{
			prime[j] = 1;
		}
	}
	//int count=0;
	for (int i = m; i <= n; i++) //n
	{
		if (prime[i] == 0)
		{
			printf("%d\n", i);
		//	count++;
		}
	}
	//printf("%d", count); //2~1000000>> 78498
	return 0;
}

sunhong 7년 전 1

18번 줄 수정이 필요할것 같습니다.

3 4를 입력하면 3이 출력이 돼야겠지요?

rim0621 7년 전 0

18번줄 sqrt(n)을 n으로 했습니다. 그런데도 런타임 에러가 뜨네요..ㅠㅠ

yclock 7년 전 0

일단, O(n+n+nsqrt(n))는 O(n sqrt(n))으로 표기합니다.

yclock 7년 전 1

배열 prime에서 prime[n]을 참조하기 때문에, 이 배열의 size는 최소 n+1이여야 합니다.

그냥 배열을 씁시다... 포인터 시러...

소수 판별 부분에서, sqrt(n)까지 검사해야 합니다.

sqrt(n)을 사용하는 것은 부동소수점 오류 때문에 사용하지 않는 것이 좋습니다.

따라서, i < sqrt(n)는 i*i < n으로 고치는 것이 좋습니다.

yclock 7년 전 1

확인해 보지는 않았습니다만, 이 문제는 O(n sqrt(n)) 알고리즘으로는 TLE를 받을 확률이 매우 높습니다.

O(n log n) 알고리즘을 생각해보는 것이 어떨까요....

rim0621 7년 전 1

배열을 1개 더 주니깐 됬네요!! 감사합니다. 더욱 열심히 할께요 ㅎㅎ

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