글 읽기 - 1%에서 시간 초과가 떠요ㅠㅠㅠㅠ

051ssaa 3년 전 0

실제로 시간 재서 돌려보면 1초 내로 잘 돌아가는데 뭐가 문제일까요..??

도와주세요ㅠㅠㅠ

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

vector<int> primeList;

int nextPrime(int prime) {
	int isPrime;
	if (prime == 2) return 3;
	for (prime+=2; ; prime+=2) {
		isPrime = 1;
		for (int i = 0; primeList[i] <= sqrt(prime); i++) {
			if (prime % primeList[i] == 0) {
				isPrime = 0;
				break;
			}
		}
		if (isPrime) return prime;
	}
}
int main() {
	int N = 0;
	int prime = 2;
	primeList.push_back(2);

	cin >> N;
	if (N == 1) return 0;

	for (; N != 1 ; ) {
		if (N % prime == 0) {
			N = N / prime;
			cout << prime << endl;
		}
		else {
			prime = nextPrime(prime);
			primeList.push_back(prime);
		}
	}
	return 0;
}

ehdrmsl2001 3년 전 2

9,999,991 이런 거 넣어보시면 1초 안에 안 나옵니다.

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

문제

문제

출처

ICPC

1%에서 시간 초과가 떠요ㅠㅠㅠㅠ

051ssaa 3년 전 0

ehdrmsl2001 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말