• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Generator liczb pierwszych PRIME1

Object Storage Arubacloud
0 głosów
175 wizyt
pytanie zadane 17 stycznia 2019 w SPOJ przez tornskin Nowicjusz (210 p.)

Cześć!

 

Mam problem z zadaniem PRIME1 - Prime Generator. Z początku dostawałem komunikat time limit exceeded, jednak po dodaniu zakresu czas znacznie się zmniejszył i przeszedłem do błędu o nazwie wrong answer. Do rozwiązania problemu użyłem sita Eratostenesa i wszystkie sprawdzenia których dokonywałem przechodził prawidłowo. Bardzo proszę o pomoc. Dodam na swoją obronę że dopiero zaczynam swoją przygodę z C++ smiley

 

Dziękuję i pozdrawiam!

#include <iostream>
#include <cstdlib>
#include <cmath>

using namespace std;

int main()
{
    int t=1,cykle;                      //ilosc cykli
    unsigned int m,n,i,w;       //poczatek zakresu, koniec zakresu
    bool *tablica;

    cout<<"wprowadz ilosc cykli: ";
    cin>>cykle;
    if (cykle>10) return 0;

    while (cykle>=t)
    {
    cout << "Wprowadz zakres dolny i gorny przedzialu oddzielony spacja: " << endl;
    cin >>m>>n;
    if (m<=1||m>=n||n>=1000000000||n-m>=100000) return 0;
    tablica=new bool[n+1];

        for (i=2;i<=n;i++)
            {
            tablica[i]=true;
            }

        for (i=2;i<=n;i++)
            {
            if (tablica[i])
            for (int w=i*i;w<=n;w+=i) tablica[w]=false;
            }

        for(i=m;i<=n;i++)
            {
            if (tablica[i]) cout<<i<<endl;
            }
    t++;
    }

    delete []tablica;

    return 0;
}

 

komentarz 17 stycznia 2019 przez krawiecki Początkujący (490 p.)
A próbowałeś usunąć wszystkie cout'y? w sesnie bez "podaj ilosc cykli" itd wydaje mi się, że spoj zwraca uwagę co jest w outpucie do tego stopnia, że kiedyś zapomniałem dać endlajna i mi nie przyjął rozwiązania. No i oczywiście wynik musisz wypisać dokładnie w ten sposób jak w przykładzie

1 odpowiedź

0 głosów
odpowiedź 18 stycznia 2019 przez tornskin Nowicjusz (210 p.)

Wkradł się mały błąd do warunków dotyczący mniejszości. Poprawiłem kod na poniższy, jednakże wracamy do TLE. problemem jest pamięciożerność sita, które wykrzacza się gdzieś w okolicach miliona operacji. Max n wynosi 10^9. 

 

#include <iostream>
#include <cstdlib>
#include <cmath>

using namespace std;

int main()
{
    int t=1,cykle;
    unsigned int m,n,i,w;
    bool *tablica;

    cin>>cykle;
    if (cykle>10) return 0;

    while (cykle>=t)
    {
    cin >>m>>n;
    if (m<1||m>n||n>=1000000000||n-m>=100000) return 0;
    tablica=new bool[n+1];

        for (i=2;i<=n;i++)
            {
            tablica[i]=true;
            }

        for (i=2;i<=n;i++)
            {
            if (tablica[i])
            for (int w=i*i;w<=n;w+=i) tablica[w]=false;
            }

        for(i=m;i<=n;i++)
            {
            if (tablica[i]) cout<<i<<endl;
            }
    t++;
    }

    delete []tablica;

    return 0;
}

 

Podobne pytania

0 głosów
1 odpowiedź 280 wizyt
0 głosów
1 odpowiedź 560 wizyt
0 głosów
0 odpowiedzi 115 wizyt
pytanie zadane 11 maja 2019 w SPOJ przez BinaryMan Stary wyjadacz (12,620 p.)

92,669 zapytań

141,567 odpowiedzi

320,034 komentarzy

62,034 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...