SPOJ - Dyzio - jak usprawnić?

0

Cześć!
Mam pytanie, napisalem prosty programik realizujacy zadanie : http://pl.spoj.com/problems/DYZIO2/
Oto kod(wstawiam, bo krotki)

#include <cstdio>

int licz(int tab[],int od,int dok);

const int wlk=1000000;

int tab[wlk];
int przed[wlk];

int main() {
    int m,a,b;
    int poprz=0;
    int *w=new int[0];
     for(int i=0;i<=(wlk-2);i++) {
        tab[i]=i+2;
    }
    for(int i=0,j;i<=(wlk-2);i++) {
        if(tab[i]!=0) {
            j=i;
            poprz++;
            while(1) {
                j+=i+2;
                if(j>(wlk-2)) break;
                tab[j]=0;
            }
        }
        przed[i]=poprz;
    }
    scanf("%d",&m);
    for(int i=0;i<m;i++) {
        scanf("%d",&a);
        scanf("%d",&b);
        if(b==2) printf("1\n");
        else printf("%d\n",przed[b-2]-przed[a-3]);
    }
    return 0;
}

Tyle, ze program wykonuje sie okolo 70s a najlepsze wyniki sa rzedu jednej setnej. Moze ktos podpowiedziec jak usprawnic taki program? Jaka strukture danych wyrzkosytac czy co zmienic.
Z gory dzieki,
Pozdrawiam

0

Poczytaj o sicie Erastotenesa i pomyśl jak wtedy to miało by działać.

0

Przeciez w moim programie zastosowalem sito.

0

O ile mi się coś na oczy nie rzuciło to nawet nie szukasz liczb pierwszych, a co dopiero przez sito. No chyba że to jakaś mocno dziwna interpretacja bo szczerze mówiąc nie bardzo rozumiem co ty w tym programie robisz. Masz co prawda deklarację funkcji licz, ale definicji ani odwołań do niej już nie widzę, ani ctrl +f nie znajduje.

edit: działa komuś to zadanie? dla programu który taki zestaw
3
6 19
2 1000000
12 50
liczy w około 0,12s mam timeouta.

0

Najprostszy algorytm jaki znam na liczby pierwsze(nie wiem może istnieje jeszcze jakiś lepszy algorytm):

 

#include <iostream>
int czyPierwsza(int liczba) {
    int i = 2;
 
    if(liczba == 1) {
        return 0;
    }
    while(1) {
        if(liczba == i) {
            return 1; //true
        }
        if((liczba % i) == 0) {
            return 0; //false
        }
        i++;
    }
}

int main()
{
    for(int i = 1; i < 100; i++) {
     if(czyPierwsza(i)) {
         std::cout <<i<<" -liczba jest pierwsza\n";
     }
     else {
      std::cout <<i<<" -liczba nie jest pierwsza\n";   
     }
    }
    
    std::cin.ignore();
    std::cin.get();

}


0

Stablicuj wyniki.

1

@robcio srsly, nie wiesz czy istnieje lepszy? A powiedz po co sprawdzasz na przykład wszystkie liczby parzyste, skoro tylko 2 jest liczbą pierwszą? To już ci ucina czas szukania o połowę...
Powiedz mi czemu sprawdzasz dzielniki aż do n, skoro RÓŻNYCH dzielników będziesz miał raptem pierwiastek z n? (czemu? bo jeśli szukasz np. dzielników 16 to będziesz miał 116, 28, 44, 82, 16*1, jak widzisz liczby się powtarzają i "różne" dzielniki występują tylko do pierwiastka z n) To znów ucina ci obliczenia dość znacznie.

0

Swoją drogą idzie komuś to zadanie? na ideone mam czas 0,3s dla zestawu
3
6 19
12 50
2 1000000
A spoj timeoutuje.

0

podpowiedź: a ile czasu twój program będzie zliczał:
10
2 1000000
2 1000000
2 1000000
2 1000000
2 1000000
2 1000000
2 1000000
2 1000000
2 1000000
2 1000000

0

masz mój:

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define MAX 999983

void sieve(vector<int>& out)
{
  vector<bool> isNotPrime(MAX + 1, false);
  isNotPrime[0] = isNotPrime[1] = true;
  for (int i = 2; i <= MAX; i++)
  {
      if (!isNotPrime[i])
      {
          out.push_back(i);
          for (int j = 2 * i; j <= MAX; j += i)
          {
              isNotPrime[j] = true;
          }
      }
  }
}

int numberOfPrimes(int a, int b, const vector<int>& s)
{
    return upper_bound(s.begin(), s.end(), b) - lower_bound(s.begin(), s.end(), a);
}

int main()
{
  vector<int> s;
  s.reserve(78498);
  sieve(s);

  int t;
  scanf("%d", &t);
  while (t--)
  {
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%d\n", numberOfPrimes(a, b, s));
  }
  return 0;
}
0

Witam wszystkich,
Mi również wyskakuje błąd przekroczenia limitu czasu
Czy ktoś mógłby mi podpowiedzieć, co mógłbym zrobić lepiej? To mój pierwszy post na tym forum, jak piszę w złym miejscu proszę poprawcie mnie + prosze o cierpliwość, jestem bardzo początkujący w dziedzinie programowania.

#include <iostream>
#include <stdio.h>

void sito(bool *tab,   int n)
{
 
    for ( int i=2; i*i<=n; i++)
    {
        if(tab[i])
        {
            for ( int j = i*i ; j<=n; j+=i)
                tab[j] = 0;
        }


    }
}
int main()
{
    int test;
    scanf("%d",&test);
    for( int t=0; t<test; t++)
    {
        int suma=0;
        bool *tab;
        int dolny, gorny;
        scanf("%d%d",&dolny,&gorny);
        tab=new bool [gorny+1];
        for( int i=1; i<=gorny; i++)
        {
            tab[i]=1;
        }
        sito(tab,gorny);
        for( int i=dolny; i<=gorny; i++)
        {
            if(tab[i])
            {
                suma+=1;
            }
        }
        printf("%d ",suma);
        delete [] tab;
    }

    return 0;
}


 
0

Przede wszystkim dlaczego za każdym razem liczysz sito od początku? Możesz to zrobić raz na początku, a potem tylko korzystać z wyliczonych raz danych. W warunkach zadania podane jest, że liczba testów może się wahać w przedziale [1,20000], więc sam widzisz, że w skrajnym przypadku liczysz 20000 razy sito, co nie jest rozsądne. Policz sito raz dla zakresu [2,10^6] i spokój. To na początek. W kolejnym kroku można w dodatkowej tabeli trzymać liczbę liczb pierwszych mniejszych równych x ( https://pl.wikipedia.org/wiki/Funkcja_%CF%80 ). Wtedy wyznaczenie wyniku dla zadania będzie trywialne.

1 użytkowników online, w tym zalogowanych: 0, gości: 1