글 읽기 - c 시간초과 뭐가 문제인지 모르겠어요ㅠㅠ

antepost24 3년 전 0

20퍼에서 시간초과가 나오네요 비주얼로 123456 넣으면 바로바로 나오는데..뭐가 문제일까요

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

int main() {
	int n = 1, i, j, k = 0, count = 0, t = 0, scount = 0;
	int arr[500] = { 0 };

	for (i = 2; i < 500; i++) {
		for (j = 2; j < i; j++) {
			if ((i % j) == 0) {
				count++;
			}
		}
			if (count == 0) {
				arr[t] = i;
				t++;
			}
		
			count = 0;
		

	}

	
	while (1) {
		scanf("%d", &n);
		if (n == 0) {
			return 0;
		}

		if (n == 1) {
			printf("1\n");
		}
		else if (n == 2) {
			printf("3\n");
		}

		else {
			for (i = n+1; i < (2 * n) + 1; i++) {
				while ((arr[k] * arr[k]) <= i) {
					
					if (i % arr[k] == 0) {
						count++;
					}
					k++;
				}
				if (count == 0) {
					scount++;
				
				}
				count = 0;
				k = 0;
			}


			printf("%d\n", scount);
			scount = 0;
		}

	}
	return 0;
}

pichulia 3년 전 0

i가 소수인지를 O(sqrt(i))번의 연산을 통해 확인하고 계신데... 이를 O(1) 급으로 수정해야합니다.

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

문제

문제

출처

ICPC

c 시간초과 뭐가 문제인지 모르겠어요ㅠㅠ

antepost24 3년 전 0

pichulia 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말