PRIME1 - Prime Generator - Zbyt długi czas działania programu

Question

Witam! Od kilku dni zmagam się z jednym zadaniem z anglojęzycznego SPOJ'a, jakim jest "Prime Generator"

Treść zadania: http://www.spoj.com/problems/PRIME1/

Moim problemem jest to, że program działa za długo i za każdym razem wywala komunikat time limit exceeded. Mój kod wygląda następująco:

#include <iostream>

void sieve_of_eratosthenes(unsigned int M,unsigned int N);

int main()
{
    unsigned int t,m,n;
    std::cin>>t;
    for (int i=0;i<t;++i)
    {
        std::cin>>m>>n;
        sieve_of_eratosthenes(m,n);
    }
    return 0;
}

void sieve_of_eratosthenes(unsigned int M,unsigned int N)
{
    bool numbers[N+1]={};
    for (int i=2;i*i<=N;++i)
    {
        if(!numbers[i])
        {
            for (int j=i*i;j<=N;j+=i)
                numbers[j]=1;
        }
    }
    for (int i=M;i<=N;++i)
    {
        if (!numbers[i] && i!=1)
            std::cout<<i<<std::endl;
    }
}

Czy ktoś mógłby mi doradzić co powinienem zmienić, abym mógł otrzymać wynik pozytywny? Dodam, że bardzo mi zależy, abym mógł uzyskać czas 0:00 (Celuje jak najwyżej :D)

Comments

Zła kategoria (SPOJ)

---

Poprawione, dziękuję.

---

@Kamil Paradowski, Możesz spróbować zrobić to bez funkcji ponieważ każde odniesienie się do funkcji troche czasu zajmuje 

 

Answer 1

Tak na szybko:

Spróbuj zamienić cout na printf, bo wiem ze były takie zadania, w których te kilka nanosekund na każdy print robiło różnicę.

Comments

Nie działa

---

zamian std::endl na "\n"