cimky 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: #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/1OCux9Natomiast SPOJ mówi: runtime error (SIGABRT) Nie wiem o co biega, proszę o pomoc :D |
|
michal11 |
» 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 #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 |
|
mateczek |
» 2016-11-30 04:31:30 |
|
cimky 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_EratostenesaProgram 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ść :) |
|
michal11 |
» 2016-11-30 12:56:56 W takim razie Zajrzyj do linka który podałem, tam jest sporo ciekawych implementacji. |
|
cimky 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ść :) |
|
michal11 |
» 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 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 #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;
}
|
|
| « 1 » |