ijm91   8년 전

에라토스테네스 이용해서 했는데시간초과뜨네요..ㅠㅠ

if(i<a)  이건 3 16 입력했을때, 2까지 소수로 담아버려서.. 그거 구분하려고 했습니다..

근데 이걸 붙이면 시간초과가 뜨고, 

저 분기문을 빼면 출력초과가 뜨네요.. 어디가 잘못된걸까요??


밑에 for 문돌린거 안으로 넣어줘도 출력초과가...ㅠㅠ

yclock   8년 전

소스가 잘 이해되지는 않지만,

예를 들어 어떤 자연수 N이 소수인지 판별하기 위해서는,

2부터 N-1까지 다 나누어보면서 확인하는 방법도 있겠지만,

2부터 sqrt(N)까지만 검사하는 방법도 있습니다.

이 방법이 되는 이유는 귀류법으로 증명할 수 있습니다.


이를 그대로 구현하면, 시간복잡도는 O(sqrt(2) + sqrt(3) + ... + sqrt(N)) => O(N log N) 정도 됩니다.


제 생각이지만, 위에 있는 소스는 O(N^2)가 아닐 듯 싶네요.

쓰다보니 알았는데, N의 정의를 적지 않았다...

immanuel   8년 전

맨 밑에 출력을 ostream이 아닌 printf()로 바꾸시면 통과 합니다.

yclock   8년 전

으악! 소스를 잘 못 이해했군요!

죄송합니다!!!

wjddnjs8862   7년 전

#include <stdio.h>

#include <stdlib.h>

int main(){

    int m,n;

    scanf("%d %d",&m,&n);

    int by;

    int cnt=0;

    for(int i=1;i<=n;i++){

        by=0;

        for(int j=1;j<=i;j++)if(i%j==0)by++;

        if(by==2)if(i>=m)printf("%d\n",i);

    }

    return 0;

}

음 이게 컴파일해보면 잘 돌아가는데 틀리다고 하는 이유가 먼지 모르겠네요.

혹시 범위를 설정해야하는것이면, 어떻게 해야하나요?


yclock   7년 전

위의 소스는 소수의 정의를 바탕으로 아주 충실하게 구현되어 있습니다. (cnt변수는 왜 있는지 모르겠군요;;)

그러나 위 소스의 시간복잡도는 O(N2)이며, M과 N이 모두 106이하인 이 문제에 대해서는 제한 시간 내에 풀 수 없습니다.


문제를 잘 읽어보시면 M이상 N이하의 모든 소수를 출력하라고 했기 때문에 중간에 for문은 다음과 같이 고쳐져야 합니다.

yclock   7년 전

여담입니다만, 예제의 답도 나오지 않을 것 같습니다....

wjddnjs8862   7년 전

예제의 답은 그대로 잘 나옵니다. 그리고cnt변수는 모르고 안지워서 남아있는거였습니다. 

궁금한것이 있는데 m과 n의 범위를 설정할수 있는 방법은 없나요? 

예를들어 

1<=m,n<=100,000 이런식으로

궁금중입니다.

wjddnjs8862   7년 전

108f1d67774564e4a294bf4a5116d3de.png

yclock   7년 전

M과 N의 범위를 설정한다는 말이 어떤 의미인지 모르겠군요...

yclock   7년 전

아니면 이런거?

wjddnjs8862   7년 전

두번째 방식을 말하는거에요. 저렇게 하면 최대값과 최소값을 정할수 있으니까 저거 사용하면 되는건가요?

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