글 읽기 - 왜 시간초과일까요....도와주세요 ᅲᅲ

(追記) (追記ここまで)

왜 시간초과일까요....도와주세요 ᅲᅲ

2986번 - 파스칼

xowns9418 8년 전 0

문제를풀기위해 N을 제외한 N의 약수중 최대값을 찾는 것이 문제의 답을 찾는 것이라 생각하였습니다.

일반적으로 N을 제외한 N의 약수중 최대값은 N/2부터 1씩 감소시키면서 검사해주면 될거라 생각하였습니다.

그런데 소수의경우는 1이므로 N이 소수인 경우와 소수가 아닌 경우를 나누어 생각하였습니다. 문제의 N최대범위인 10^9을 넣어도 바로 출력이되는데 왜 시간초과가 나는걸까요??

#include<iostream>
using namespace std;
bool isprime(int n) {
	if (n == 1)
		return false;
	else {
		for (int i = 2; i*i <= n; i++) {
			if (n%i == 0) {
				return false;
			}
		}
	}
	return true;
}
int main(void) {
	ios::sync_with_stdio(false);
	int N;
	cin >> N;
	if (isprime(N)) { //소수 일 경우
		cout << N - 1 << '\n';
	}
	else {
		for (int i = N / 2; 0 < i; i--) {//소수가 아닐 경우 N/2부터 1씩 감소시키면서 탐색
			if (N%i == 0) {
				cout << N - i << '\n';
				break;
			}
		}
	}
	return 0;
}

xowns9418 8년 전 0

해결햇습니다 감사합니다!!

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

왜 시간초과일까요....도와주세요 ᅲᅲ

xowns9418 8년 전 0

xowns9418 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말