Szukanie liczb pierwszych w przedziale - problem z liczbami większymi niż 201
Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Zarejestruj się!

Szukanie liczb pierwszych w przedziale - problem z liczbami większymi niż 201

AutorWiadomość
Temat założony przez niniejszego użytkownika
Szukanie liczb pierwszych w przedziale - problem z liczbami większymi niż 201
» 2016-11-29 16:37:41
Witam.

Próbuję rozwiązać problem wyszukiwania liczb pierwszych z określonego przez użytkownika przedziału. Całe zadanie dostępne pod linkiem:

http://www.spoj.com/problems​/PRIME1/

Moja implementacja:

C/C++
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
    short ilebadan;
    cin >> ilebadan;
   
    short * badanie = new short[ ilebadan ];
   
    int * odilu = new int[ ilebadan ];
    int * ile = new int[ ilebadan ];
   
    for( int x = 0; x < ilebadan; x += 1 )
    {
        cin >> odilu[ x ] >> ile[ x ];
    }
   
    for( int x = 0; x < ilebadan; x += 1 )
    {
        bool * booltab = new bool[ ile[ x ] ];
       
        for( int i = 0; i < ile[ x ]; i += 1 )
        {
            booltab[ i ] = true;
        }
       
       
        for( int i = 2; i <=( sqrt( ile[ x ] ) ); i += 1 )
        {
           
           
            if( booltab[ i - 2 ] == true )
            {
               
                int j = 0;
                for( int it = 0; j <=( ile[ x ] + 1 ); it += 1 )
                {
                    j =(( i * i ) +( it * i ) );
                   
                    booltab[ j - 2 ] = false;
                }
            }
        }
       
        for( int i = 0; i < ile[ x ]; i += 1 )
        {
            if( booltab[ i ] == true &&( i + 2 ) >= odilu[ x ] &&( i + 2 ) <= ile[ x ] ) cout <<( i + 2 ) << endl;
           
        }
        cout << endl;
    }
    delete[] badanie;
    delete[] odilu;
    delete[] ile;
}

Maksymalny przedział, dla którego Visual Studio trawi program to: <0;201>
Jeśli damy przedział np <23; 202> to pojawiają się problemy:

Visual Studio mówi mi, że program "has triggered a breakpoint.", oraz "wntdll.pdb not loaded". Visual na chwilę się zawiesza itd.


Żeby było zabawniej, na Ideone.com wszystko prawidłowo, dla dowolnych przedziałów:

http://ideone.com/1OCux9

Natomiast SPOJ mówi: runtime error (SIGABRT)

Nie wiem o co biega, proszę o pomoc :D




P-154281
» 2016-11-29 23:47:03
Nie wiem co robisz w swoim algorytmie ale wydaje mi się, że zdecydowanie przesadziłeś ze skomplikowaniem kodu. Moim zdaniem wystarczy coś podobnego
C/C++
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>

//====================================================================================================================
bool isPrime( int num )
{
    if( num == 1 ) { return false; }
   
    for( int i = 2; i < num; ++i )
    {
        if( num % i == 0 )
        {
            return false;
        }
    }
    return true;
}

const std::vector < int >& getPrimeNumbers( int Begin, int End )
{
    static std::vector < int > cachedPrimeNumbers;
   
    for( int i = Begin; i <= End; ++i )
    {
        if( std::find( cachedPrimeNumbers.cbegin(), cachedPrimeNumbers.cend(), i ) == cachedPrimeNumbers.cend() )
        {
            if( isPrime( i ) )
            {
                cachedPrimeNumbers.push_back( i );
            }
        }
    }
   
    return cachedPrimeNumbers;
}

void print( std::ostream & out, const std::vector < int >& arr, int begin, int end )
{
    auto beginRange = std::lower_bound( arr.cbegin(), arr.cend(), begin );
    auto endRange = std::upper_bound( arr.cbegin(), arr.cend(), end );
   
    std::copy( beginRange, endRange, std::ostream_iterator < int >( out, "\n" ) );
}

int main()
{
    int t;
    std::cin >> t;
   
    int m, n;
   
    for( int i = 0; i < t; ++i )
    {
        std::cin >> m >> n;
       
       
        const std::vector < int >& primeNumbers = getPrimeNumbers( m, n );
       
        print( std::cout, primeNumbers, m, n );
        std::cout << std::endl;
    }
   
    return 0;
}

jeżeli będzie za wolne to możesz zainteresować się sitem eratostenesa.

albo tez tutaj możesz znaleźć coś ciekawego http://stackoverflow.com​/questions/1042902​/most-elegant-way-to-generate-prime-numbers
P-154314
» 2016-11-30 04:31:30
P-154320
Temat założony przez niniejszego użytkownika
» 2016-11-30 09:12:09
Sęk w tym, że mój program opiera się właśnie na Sicie Eratostenesa
https://pl.wikipedia.org/wiki​/Sito_Eratostenesa

Program działa świetnie, dla liczb mniejszych od 202. Jego wadą, którą na pewno wyeliminuję jest fakt, że mimo, iż użytkownik poda przedział szukania liczb pierwszych np. taki: <100; 200> to program tworzy tablicę booli od 0 do 198, choć wystarczyłaby od 0 do 98, a na koniec programu każdy nr tablicy zwiększyć o 100 i mamy liczbę pierwszą.

Zupełnie nie rozumiem, dlaczego wyrzuca błąd i chciałbym właśnie na ten moment nie tyle szukać innego rozwiązania, lecz zrozumieć co jest nie tak w tym kodzie, aby nie powielać błędu na przyszłość :)
P-154326
» 2016-11-30 12:56:56
W takim razie Zajrzyj do linka który podałem, tam jest sporo ciekawych implementacji.
P-154335
Temat założony przez niniejszego użytkownika
» 2016-11-30 13:23:09
Zupełnie nie rozumiem, dlaczego wyrzuca błąd i chciałbym właśnie na ten moment nie tyle szukać innego rozwiązania, lecz zrozumieć co jest nie tak w tym kodzie, aby nie powielać błędu na przyszłość :)
P-154336
» 2016-11-30 15:01:21
Próbowałem zdebuggowac twój program, warto tu zaznaczyć, że masz wycieki pamięci na booltab, i wychodzisz poza zakres tej tablicy w linijce
booltab[ j - 2 ] = false;
.

A twoja tablica booltab ma taki rozmiar jaki jej przekazujesz czyli zawsze jest to górna granica przeszukiwanego przedziału
C/C++
for( int x = 0; x < ilebadan; x += 1 )
{
    cin >> odilu[ x ] >> ile[ x ];
}

for( int x = 0; x < ilebadan; x += 1 )
{
    bool * booltab = new bool[ ile[ x ] ];

Przerobiłem na swoje potrzeby trochę twój program, może to ci pomoże znaleźć błąd
C/C++
#include <iostream>
#include <math.h>
#include <vector>
using namespace std;
int main()
{
    short ilebadan;
    cin >> ilebadan;
   
    vector < short > badanie( ilebadan );
   
    vector < int > odilu( ilebadan );
    vector < int > ile( ilebadan );
   
    for( int x = 0; x < ilebadan; x += 1 )
    {
        cin >> odilu[ x ] >> ile[ x ];
    }
   
    for( int x = 0; x < ilebadan; x += 1 )
    {
        vector < bool > booltab( ile[ x ] );
       
        for( int i = 0; i < ile[ x ]; i += 1 )
        {
            booltab[ i ] = true;
        }
       
        for( int i = 2; i <=( sqrt( ile[ x ] ) ); i += 1 )
        {
            if( booltab[ i - 2 ] == true )
            {
                int j = 0;
                for( int it = 0; j <=( ile[ x ] + 1 ); it += 1 )
                {
                    j =(( i * i ) +( it * i ) );
                   
                    booltab[ j - 2 ] = false;
                }
            }
        }
       
        for( int i = 0; i < ile[ x ]; i += 1 )
        {
            if( booltab[ i ] == true &&( i + 2 ) >= odilu[ x ] &&( i + 2 ) <= ile[ x ] ) cout <<( i + 2 ) << endl;
           
        }
        cout << endl;
    }
   
    return 0;
}
P-154343
« 1 »
 Strona 1 z 1