Liczby pierwsze, sito eratostenesa
Ostatnio zmodyfikowano 2016-10-31 21:10
matevos Temat założony przez niniejszego użytkownika |
Liczby pierwsze, sito eratostenesa » 2016-10-31 17:45:30 Witam, przez ostatnie dni borykam się z pewnym zadaniem o treści. "Napisz program, który dla podanej liczby x<10000000 rozstrzyga czy jest ona liczbą pierwszą. Jeśli x nie jest liczbą pierwszą - program wypisuje na ekranie wiersz postaci "x nie jest pierwsza." W przeciwnym wypadku - program powinien określić, którą z kolei liczbą pierwszą jest x oraz wypisać na ekranie wiersz postaci "x to liczba pierwsza numer nr."" Całe zadanie wydaje się być banalne jednakże problem tkwi w tym, iż przez system uczelniani na którym oddaje zadanie jest ustawiony limit pamięci 8MB. Stosując nawet najmniejszy rodzaj zmiennej typu char dla zbioru x i tak będzie zapotrzebowanie w postaci 10MB by wygenerować całą listę za pomocą sita. Pomyślałem w takim razie, by rozwiązać ten problem w ten sposób, aby na jednym elemencie tablicy char zapisywać informacje o 8 liczbach na 8 bitach w postaci binarnej '1' nie jest pierwszą, '0' jest pierwszą. Dzięki temu zaoszczędziłbym trochę pamięci i zmieściłbym się dużo poniżej limitu 10000000/8 = 1250000 bajtów = 1,25 MB. Jednak niestety pojawia się problem z implementacją tego rozwiązania, nie za bardzo wiem jak za to się zabrać. Dlatego prosiłbym o pomoc lub naprowadzenie mnie na jakiś inny i może łatwiejszy pomysł. Chciałbym jeszcze wspomnieć, że dopiero co zacząłem swoją przygodę z C++ tak więc nie za bardzo są mi znane te bardziej zaawansowane techniki, które zapewne ułatwiłby wykonanie zadania. To jest mój aktualny kod testowy. #include <iostream>
using namespace std;
int main() {
char tab[ 1250000 ];
int n;
for( int i = 2; i <= 1250000; i++ ) {
tab[ i ] = '0';
}
for( int i = 2; i * i <= 1250000; i++ ) {
if( tab[ i ] == '0' ) {
for( int j = i * i; j <= 1250000; j += i ) {
tab[ j ] = '1';
}
}
}
cin >> n;
for( int i = 2; i <= n; i++ ) {
if( tab[ i ] == '0' ) {
cout << i << " ";
}
}
return 0;
}
|
|
michal11 |
» 2016-10-31 17:56:30 |
|
matevos Temat założony przez niniejszego użytkownika |
» 2016-10-31 19:16:02 Dziękuje bardzo, zadanie rozwiązałem :) |
|
michal11 |
» 2016-10-31 21:10:36 Z ciekawości z czego skorzystałeś? |
|
| « 1 » |