글 읽기 - 시간초과가 나는데 갈피가 안잡힙니다. 도움 부탁드립니다.

yeongmo 5년 전 0

처음에 앞에서부터 해왔던대로

배열을 이용해 수가 입력될 때마다 소수배열을 새로만들고 답을 구했더니 시간초과가 나서

아예 최대입력숫자까지 나눗셈 방식으로 판별해가며 소수를 다 판별한 뒤에 해도 시간초과가 나서

질문게시판에 올라온 답변처럼 에라토스테네스의 체를 이용해서 소수를 처음에 구하고 해봐도 시간초과가 납니다..ㅠㅠ

더이상 더 어떻게 빠르게 만들 수가 있을지...

지금의 제 능력 밖의 문제인걸까요?

#include <stdio.h>

void Prime(int primes[],int n) //에라토스테네스의 체 (primes[인덱스]의 숫자가 1이면 인덱스에 해당하는 숫자가 소수가 아닌 것)
{
    int i,j;
    for (i=2 ; i*i<=n ; i++)
    {
        for (j=2 ; i*j<=n ; j++)
        {
            primes[i*j]=1;
        }
    }
}

int Goldbach(int primes[],int n,int count,int *f, int *e)
{
    int i,j;
    int front,end;
    int result=0;
    for (i=0 ; i<count; i++)
    {
        for (j=count ; j>0 ;j--)
        {
            if (i>j)
                break;
            if (primes[j]+primes[i]==n)
            {
                front=i;
                end=j;
                result=1;
            }
        }
    }
    if (result==1)
    {
        *f=front;
        *e=end;
        return 1;
    }
    else
        return 0;
}

int main(void)
{
    int prime[10001]={1,1,}; //에라토스테네스의 체를 위한 배열
    int realprime[10000]={0,}; //에라토스테네스의 체에서 소수들만을 걸러낼 배열
    int n,T;
    int i,j,js=0;
    int result=0;
    int F,E;
    
    Prime(prime, 10000); //에라토스테네스의 체 실행
    for (j=0 ; j<=10000; j++) // 그 중에 소수들만 골라내서 새 배열에 저장
    {
        if (prime[j]==0)
        {
            realprime[js]=j;
            js++;
        }
    }
    //js는 소수의 총 개수
    
    scanf("%d",&T);
    
    for (j=0 ; j<T ; j++)
    {
        scanf("%d",&n);
        for (i=0 ; i<=js ; i++)
        {
            if (n<realprime[i])
                break;
        }
        result=Goldbach(realprime, n, i, &F, &E);
        if (result==1)
        {
            printf("%d %d\n",realprime[F],realprime[E]);
        }
    }
    return 0;
}

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

문제

문제

출처

ICPC

시간초과가 나는데 갈피가 안잡힙니다. 도움 부탁드립니다.

yeongmo 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말