글 읽기 - [C] 시간초과,,

cyunchaeskku 2년 전 0

수학시간에 배웠던 에라토스테네스의 체 과정을 그대로 코드로 옮겨보았는데, 계속 시간초과가 뜨네요..

이런 식으로 푸는 게 아닌걸까요?

고수 분들 많은 도움 부탁드립니다ㅠ 감사합니다.

#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0

int define_prime(int n)
{
    int flag=1;
    if(n==1 || n==0)    return FALSE;
    else if(n==2)   return TRUE;
    else
    {
        for(int i=2;i<n;i++)
        {
            if(n%i==0)
            {
                flag=0;
                break;
            }

        }
        if(flag==1)    return TRUE;
        else    return FALSE;
    }
}

int main()
{
    int m,n;
    int temp;
    int idx=1;
    scanf("%d %d",&m,&n);
    int *arr=(int*)malloc(sizeof(int)*(n-m+1));
    for(int i=0;i<=n-m;i++)
    {
        arr[i]=m+i;
        if(arr[i]>2 && arr[i]%2==0) arr[i]=0;
    }
    for(int i=0;i<=n-m;i++)
    {
        
        
        if(define_prime(arr[i])==TRUE)
        {
            idx=1;
            printf("%d ",arr[i]);
            while(i+arr[i]*idx<=n-m)
            {
                if(arr[i+arr[i]*idx]==0)
                {

                }
                else
                    arr[i+arr[i]*idx]=0;
                idx++;
            }
        }
        else
        {

        }
    }
    





    free(arr);
    return 0;
}

sjyfantasy 2년 전 0

에라토스테네스의 체 원리를 수학적 원리에 응용하시면 소모시간이 반 이상 줄어듭니다.

그건 반복문을 SQRT(N)까지만 돌리는 겁니다.

sjyfantasy 2년 전 0

또 에라토스테네스의 원리 중 하나가 빠지셨는데

소수를 구하면 그의 배수들도 전부 FALSE처리 해주시면 됩니다.

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

문제

문제

출처

ICPC

[C] 시간초과,,

cyunchaeskku 2년 전 0

sjyfantasy 2년 전 0

sjyfantasy 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말