Piastlis |
» 2016-06-06 23:42:57 C++ jest z jednej strony bardzo zbliżone do asemblera (możliwość korzystania ze zmiennych o wielkości jednego lub kilku bajtów) jak i do korzystania z dość skomplikowanych obiektów.Jakichś czas temu miałem podobny problem.Nie chodziło o liczby pierwsze ale o zadanie na spoj: http://pl.spoj.com/problems/TPERML/Dość infantylny algorytm ale operujący na zmiennej wielkości 100!. Poradziłem sobie w ten sposób że kalkulator operujący na tej zmiennej zaimplementowałem samodzielnie jako zmienną typu string.Kalkulator czyli + - / * mod dosłownie mieści się na 1 ekranie ,niezbędną wiedzę żeby taki kalkulator napisać masz z podstawówki..... Jeżeli chcesz dość wydajnie obliczać liczby pierwsze zainteresuj się sitami.. np. na początek Eratostenesa... |
|
oxygenium79 Temat założony przez niniejszego użytkownika |
» 2016-06-07 08:05:41 Nie, w sita nie chcę włazić, jedyne czego mi potrzeba, to GMP. W PHP udało mi się to zrobić bez problemu, a tutaj nie potrafię. |
|
Piastlis |
» 2016-06-07 11:08:33 Pomysł który przedstawił ci kol. @mateczek to właśnie proste sito Eratostenesa.Uwzględnienie liczb podzielnych przez 2 i 3 redukuje ilość obliczeń do 1/3 ale np. jeżeli uwzględnisz 2,3 i 5 to zredukujesz do 1/4 (wystarczy sprawdzić 8 wartości w grupie 30):). int kroki[ 30 ] = { 1, 6, 5, 4, 3, 2, 1, 4, 3, 2, 1, 2, 1, 4, 3, 2, 1, 2, 1, 4, 3, 2, 1, 6, 5, 4, 3, 2, 1, 2 };
for( unsigned long long k = 5; k <= max; k += kroki[ k % 30 ] ) { if( liczba % k == 0 ) { pierwsza = false; break; }
|
|
oxygenium79 Temat założony przez niniejszego użytkownika |
» 2016-06-07 12:57:16 Dzięki, ale nie. :-) Chcę tylko zmienić zmienne na GMP, żeby przekroczyć granicę 18446744073709551597. Reszta mnie nie interesuje, tyle mi wystarczy. |
|
Piastlis |
» 2016-06-07 18:45:34 Ok... Rozumiem.Ale po co Ci dodatkowa biblioteka dla działań podstawowych..+-\*%...To potrafi c++ samo z siebie...Jak GMP nie daje sobie rady to "szkoda czasu i atłasu". |
|
mateczek |
» 2016-06-07 18:49:51 biblioteka potrzebna do operacji na większych liczbach !!!! które nie mieszczą się na 64 bitach |
|
oxygenium79 Temat założony przez niniejszego użytkownika |
» 2016-06-07 20:10:44 GMP jak najbardziej daje sobie radę, ja po prostu nie potrafiłem tego napisać, nie zrozumieliśmy się. :-) Ale przysiadłem i napisałem sam, wygląda to tak i działa (choć nie tak szybko, jak poprzednia wersja bez GMP, ale za to mogą być duże liczby): #include <cstdlib> #include <iostream> #include <math.h> #include <stdio.h> #include <gmp.h> using namespace std;
int main() { cout.precision( 20 ); mpz_t liczba; mpz_init_set_str( liczba, "50446744073709551651", 10 ); mpz_t trojka; mpz_init_set_str( trojka, "3", 10 ); mpz_t p3; mpz_init_set_str( p3, "0", 10 ); mpz_t granica; mpz_init_set_str( granica, "0", 10 ); mpz_t dzielnik; mpz_init_set_str( dzielnik, "6", 10 ); mpz_t dzielnik1; mpz_init_set_str( dzielnik1, "0", 10 ); mpz_t dzielnik2; mpz_init_set_str( dzielnik2, "0", 10 ); mpz_t zmiana; mpz_init_set_str( zmiana, "1", 10 ); mpz_t reszta1; mpz_init_set_str( reszta1, "0", 10 ); mpz_t reszta2; mpz_init_set_str( reszta2, "0", 10 ); mpz_t skok6; mpz_init_set_str( skok6, "6", 10 ); mpz_t skok2; mpz_init_set_str( skok2, "2", 10 ); mpz_t iloczyn; mpz_init_set_str( iloczyn, "0", 10 ); mpz_t porownanie; mpz_init_set_str( porownanie, "0", 10 ); int sprawdzenie = 0; while( sprawdzenie == 0 ) { gmp_printf( "%s: %Zd\n", "Liczba", liczba ); sprawdzenie = 1; mpz_mod( p3, liczba, trojka ); if( mpz_cmp( p3, porownanie ) == 0 ) { sprawdzenie = 0; } else { mpz_set_str( dzielnik, "6", 10 ); mpz_sqrt( granica, liczba ); while( sprawdzenie == 1 && mpz_cmp( dzielnik, granica ) <= 0 ) { mpz_add( dzielnik1, dzielnik, zmiana ); mpz_sub( dzielnik2, dzielnik, zmiana ); mpz_mod( reszta1, liczba, dzielnik1 ); mpz_mod( reszta2, liczba, dzielnik2 ); mpz_mul( iloczyn, reszta1, reszta2 ); if( mpz_cmp( iloczyn, porownanie ) == 0 ) { sprawdzenie = 0; } else { mpz_add( dzielnik, dzielnik, skok6 ); } } } if( sprawdzenie == 1 ) { cout << endl; cout << "\t"; gmp_printf( "%s liczba jest pierwsza: %Zd\n", "Ta", liczba ); cout << endl; cout << endl; cout << "\t" << "Rekord w C++ bez GMP: 18446744073709551557 w 19 s - wiekszej liczby sie nie da bez GMP(!)."; cout << endl; cout << "\t" << "Rekord w C++ z GMP dla 18446744073709551557: 83 s - niestety, sporo wolniej."; cout << endl; cout << "\t" << "Rekord w C++ z GMP: dla 50446744073709551651 w 169 s."; } mpz_add( liczba, liczba, skok2 ); } cout << endl; return 0; }
|
|
oxygenium79 Temat założony przez niniejszego użytkownika |
» 2016-06-09 10:13:30 Haha, tylko że w ferworze walki zrobiłem w tym całym programie kardynalny błąd. Łatwo go poprawić, ale kto nie widzi, niech poczeka aż wstawię poprawioną wersję... |
|
1 2 3 « 4 » 5 6 |