Вопросы Теги

Обнаружение службы говорит, что доступ запрещен

  1. Внутренний цикл выполняет шаги n/i, где i является простым => вся сложность sum(n/i) = n * sum(1/i). В соответствии с первичными гармоническими рядами sum (1/i), где i является простым, является log (log n). В общем, O(n*log(log n)).
  2. Я думаю, что верхний цикл можно оптимизировать, заменив n на sqrt(n), поэтому общая временная сложность будет O(sqrt(n)loglog(n)): 
    void isprime(int n)
{
    int prime[n],i,j,count1=0;
    for(i=0;i<n;i++)
    {
       prime[i]=1;
    }
    prime[0]=prime[1]=0;
    for(i=2;i<=n;i++)
    {
        if(prime[i]==1)
        {
            printf("%d ",i);
            for(j=2;(i*j)<=n;j++)
                prime[i*j]=0;
        }
    }    
}
1
задан Akshay Sood 18 January 2019 в 12:31
поделиться