Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

Liczby pierwsze, sito eratostenesa

Ostatnio zmodyfikowano 2016-10-31 21:10
Autor Wiadomość
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.

C/C++
#include <iostream>

using namespace std;

int main() {
    char tab[ 1250000 ];
    int n;
   
    //zerowanie tablicy
    for( int i = 2; i <= 1250000; i++ ) {
        tab[ i ] = '0';
    }
   
    //przesianie tablicy
    for( int i = 2; i * i <= 1250000; i++ ) {
        if( tab[ i ] == '0' ) {
            for( int j = i * i; j <= 1250000; j += i ) {
                tab[ j ] = '1';
            }
        }
    }
   
    //wyswietlanie liczb pierwyszch do danego zakresu
    cin >> n;
   
    for( int i = 2; i <= n; i++ ) {
        if( tab[ i ] == '0' ) {
            cout << i << " ";
        }
    }
   
    return 0;
}
P-153119
michal11
» 2016-10-31 17:56:30
P-153122
matevos
Temat założony przez niniejszego użytkownika
» 2016-10-31 19:16:02
Dziękuje bardzo, zadanie rozwiązałem :)
P-153134
michal11
» 2016-10-31 21:10:36
Z ciekawości z czego skorzystałeś?
P-153142
« 1 »
  Strona 1 z 1