4 / 4
Mar 2020

Hello
I am trying to solve the Prime Number generator problem but I receive the Wrong Answer all the time.
Could anyone check my code? I can not figure out what is wrong.

#include
#include
#include
using namespace std;

int t = 0, m = 0, n = 0, counter = 0;
vector marks;
vector primes;
vector marks_in_range;

int main()
{
cin >> t;
while (counter < t)
{
cin >> m >> n;

    //calculate limit
    int limit = ((int)sqrt(n)) + 1;

    //fill-in table for given limit
    for (int i = 0; i <= limit; i++)
    {
        marks.push_back(true);
    }

    //find primes for given limit
    for (int i = 2; i <= limit; i++)
    {
        if (marks[i] == true)
        {
            primes.push_back(i);

            for (int j = i; j <= limit; j += i)
            {
                marks[j] = false;
            }
        }
    }

    //calculate range
    int range = n - m + 1;

    //fill-in table for given range
    for (int i = 0; i <= range; i++)
    {
        marks_in_range.push_back(true);
    }

    //use primes found for limit to find primes in range
    for (int i = 0; i < primes.size(); i++)
    {
        int loLim = ((int)(m / primes[i])) * primes[i];

        if (loLim < m)
        {
            loLim += primes[i];
        }

        if (loLim == primes[i])
        {
            loLim += primes[i];
        }

        for (int j = loLim; j <= n; j += primes[i])
        {
            marks_in_range[j - m] = false;
        }
    }

    //display primes in given range
    for (int i = m; i <= n; i++)
    {
        if (i == 1)
        {
            continue;
        }
        else if (marks_in_range[i - m] == true)
        {
            cout << i << endl;
        }
    }
    cout << endl;
    counter++;
}

return 0;

}

  • created

    Mar '20
  • last reply

    Mar '20
  • 3

    replies

  • 773

    views

  • 2

    users

  • 3

    links

To zadanie: https://pl.spoj.com/problems/PRIME_T/ rozwiązałem kilka lat temu w Javie (i zostało ono zaakceptowane). Teraz mam problem tego rodzaju, że moje rozwiązanie działa na moim kompie i na ideone.com1 a sędzia zgłasza błąd WA.
W kodzie, który zamieściłem powyżej w dyrektywach #include powinno być: iostream, vector, cmatch (wygląda na to, że edytor ucina tekst który jest w nawiasach ostrych). Starałem się zaimplementować sito Erastotenesa dla przedziału.

Do zadania prime1 nie podałeś linku, a do zadania, prime_t dajesz, mimo, że w wiadomości wyżej jest już umieszczony aż nadto wyraźnie.

To może teraz rozwiązałbyś jednak w c++ i pokazał? Na pewno to Ci nie zaszkodzi.

Więc może to pokaż, kod i wklejone testy na ideone [wklejając link]?

Dla mnie to wygląda, że nie nauczyłeś się poprawnie wklejać kodu. Przyjrzyj się uważnie swojej wiadomości. Czy to naprawdę takie trudne, zaznaczyć cały kod, a nie jego fragment i kliknąć w jedną ikonkę?

Mimo wszystko, może powinieneś zapoznać się z tekstem: Jeśli zaczynasz, przeczytaj koniecznie! <--kliknij w to proszę!