글 읽기 - 문제에서 왜 시간초과가 발생하지 않은지 궁금합니다

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

문제에서 왜 시간초과가 발생하지 않은지 궁금합니다

6588번 - 골드바흐의 추측

tpgus2603 1년 전 0

문제의 테스트케이스가 최대 10만개이고 소수검증을 해야하는 수의 최대 범위가 1백만 이여서 최악의 경우 n=10만일때 O(n^2)까지 나올거라 예측하였습니다

따라서 linear하게 판별을 하면 시간초과가 날것으로 추측하였지만 더이상 풀이가 안떠올라서 일단 제출했는데 통과를해서 의문입니다.

왜 시간초과가 발생하지않는지 궁금합니다 , 테스트케이스 크기가 10만 부근인 경우가 문제의 테스트케이스로 없어서 그럴까요?```

#include<iostream>
#include<algorithm>
using namespace std;
bool check[1000001]; //0인경우 소수 
int main()
{
 
 ios::sync_with_stdio(0);cin.tie(0);
 check[1]=true;
 for(int i=2;i<=1000;i++)
 {
 if(check[i])
 continue;
 for(int j=i;j*i<=1000000;j++)
 check[j*i]=true;
 }
 while(1)
 { 
 int n;
 cin>>n;
 if(n==0)break;
 for(int i=3;i<n;i+=2)
 {
 if(check[i]==0&&check[n-i]==0)
 {
 cout<<n<<" = "<<i<<" + "<<n-i<<'\n';
 break;
 }
 if(i==n-1)
 cout<<"Goldbach's conjecture is wrong."<<'\n';
 }
 }
}

djm03178 1년 전 1

골드바흐의 추측은 대개의 경우 아주 많은 해가 있기 때문에 이 범위 내에서는 최악의 경우에도 루프를 도는 횟수가 매우 적습니다.

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

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

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

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

한국어 | English (Beta)

문제

문제

출처

ICPC