Liczby pierwsze
Ostatnio zmodyfikowano 2016-12-26 23:46
bkjg Temat założony przez niniejszego użytkownika |
Liczby pierwsze » 2016-12-26 20:52:39 Muszę napisać program obliczający ilość liczb pierwszych w przedziale od a do b, gdzie a,b<=10^9 oraz b-a<=10^6. Otóż nie wiem, jak obliczyć ilość liczb pierwszych w tak dużym przedziale - sitem Eratostenesa nie wyjdzie, bo za duże wartości. Można co prawda skorzystać z własności b-a<=10^6, aczkolwiek nie wiem, w jaki sposób... |
|
mateczek |
» 2016-12-26 22:27:22 może zapisywanie znalezionych liczb pierwsze w tablicy i kolejne liczby sprawdzać tylko z wcześniej zapisanymi by nie jechać totalnym brutalem może ktoś sypnie lepszym pomysłem #include <iostream>
#include<cmath>
#include<vector>
using namespace std;
int main() {
vector < long long > liczbyPierwsze;
long long a, b;
cin >> a >> b;
int licznik = 0;
liczbyPierwsze.push_back( 2 );
for( long long i = 3; i <= b; i++ ) {
int max = sqrt( i );
bool pierwsza = true;
for( long long dzielnik: liczbyPierwsze ) {
if( i % dzielnik == 0 ) {
pierwsza = false;
break;
}
if( dzielnik > max ) break;
}
if( pierwsza ) {
liczbyPierwsze.push_back( i );
}
if( pierwsza &&( i >= a ) &&( i <= b ) ) {
licznik++;
}
}
cout << licznik << " ";
}
//edit sposób się nie nadaje wymaga stablicowania liczb pierwszych z przedziału<0 a> i nie nadaje się do rozwiązania zadania brutalem spróbuj !!! #include <iostream>
#include<cmath>
using namespace std;
int main() {
long long a, b;
cin >> a >> b;
int licznik = 0;
liczbyPierwsze.push_back( 2 );
for( long long i = a; i <= b; i++ ) {
int max = sqrt( i );
bool pierwsza = true;
for( int j = 2; j <= max; j++ ) {
if( i % j == 0 ) {
pierwsza = false;
break;
}
}
if( pierwsza ) {
licznik++;
}
}
cout << licznik << " ";
}
|
|
mokrowski |
» 2016-12-26 23:46:21 http://www.math.edu.pl/jak-rozmieszczone
https://en.wikipedia.org/wiki/Sieve_of_Atkin |
|
| « 1 » |