글 읽기 - 11653번 시간초과

ogt2092 3년 전 0

안녕하세요.. 고수님들

계속 시간초과가 떠서 고수님들에게 질문합니다.

제가 한 방식은 모든 소수를 S[N]에 저장한 후

주어진 값(N)을 S[0]부터 차례대로 나누는 방식입니다.

어느부분이 시간을 잡아먹는지 알고 싶어서 질문글에 올립니다.

#include<iostream>
using namespace std;
int main()
{
	int N,j=2,i,n=0,m=0;
	cin>>N;
	int S[N];
	if(N==1) N++;
	for(;j<=N;j++)
	{
		int s=1;
		for(i=2;i<j;i++)
			if(j%i==0) {s=0;break;}	
		if(s){S[n]=j;n++;}
	}
	while(N>1)
	{
		if(N%S[m]==0)
		{
			N/=S[m];
			cout<<S[m]<<endl;
			m=0;
		}
		else m++;
	}	
}

nahwasa 3년 전 1

소수 구하는 로직인 9~15line이 O(N^2) 정도 나옵니다.

N은 10,000,000 까지이므로 시간초과입니다!

ogt2092 3년 전 1

아하! 감사합니다!

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

문제

문제

출처

ICPC

11653번 시간초과

ogt2092 3년 전 0

nahwasa 3년 전 1

ogt2092 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말