글 읽기 - 시간초과문제

gusdnr9875 6년 전 0

배열에 소수점값들을 저장 해놓고 불러 오는식으로 했습니다...

어떻게 풀어야 할까요?

#include <iostream>
using namespace std;

int arr[246915] = { 0 };
int main() {

	int n = 0, cnt = 0,judge=0;
	for (int i = 2; i <246915; i++) {
		for (int j = 2; j < i; j++) {
			if (i % j == 0) {
				judge = 1;
				break;
			}
		}
		if (judge == 0)
			arr[i]=1;
		judge = 0;
	}

	while (1) {
		cnt = 0;
		cin >> n;
		if (n == 0)
			break;
		for (int i = n + 1; i <= 2 * n; i++)
			if (arr[i] == 1)
				cnt++;

		cout << cnt << endl;
	}

}

kimsy96 6년 전 1

소수를 저장하고 불러오는 방식은 정확히 집으셨읍니다만, 그 과정이 너무 느립니다

소수를 빠르게 구하는 에라토스테네스의 체 알고리즘을 공부해보세요

그리고

endl은 그냥 endl 쓰는 거 만으로도 시간초과가 날만큼 느리기 때문에

'\n'을쓰세요

gusdnr9875 6년 전 0

정말 감사합니다! 제 백준인생에 친절하고 꼼꼼하신 댓글은 처음입니다.

앞으로 열심히 해서 꼭 훌룡한 코더가 되겠습니다. 다시한번감사합니다.

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

문제

문제

출처

ICPC

시간초과문제

gusdnr9875 6년 전 0

kimsy96 6년 전 1

gusdnr9875 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말