[C++] liczba n - 1 jest iloczynem trzech różnych liczb pier


(lukasz_n) #1

Dzień dobry, chcę od razu zaznaczyć że poniżej umieszczone polecenie i program służą tylko do celów poszerzenia mojej wiedzy i umiejętności. Nie jest to żadna praca domowa czy zaliczenie.

Polecenie:

Na razie zrobiłem program wyświetlający liczby pierwsze w zakresie 0-100, ale rozszerzenie zakresu to nie problem.

#include

using namespace std;

int main()

{

int max=100;

int licznik=0;

for(int i=1; i
{

for(int j=1; j
{

if(i%j==0)

licznik++;

}

if(i==1 || licznik==1)

{

cout<
}

licznik=0;

}

cout<
system("pause");

}

[/code]

Niestety nie wiem jak się zabrać za polecenie, będę wdzięczny za każdą pomoc która pomoże rozwiązać mój problem.

Pozdrawiam

Łukasz


(Frankfurterium) #2

Zbierz liczby pierwsze do tablicy (i bądź pewny, że jest posortowana wzwyż). Mnożysz przez siebie trzy pierwsze, dodajesz 1 i masz pierwsze n. Powtarzasz procedurę dla liczb z tablicy od drugiej do czwartej. Potem od trzeciej do piątej itd. Wszystko w zgrabnej pętelce.


(Grzelix) #3

To podejście jest prawie dobre.

1*2*3 liczba pierwsza ok

2*3*4 też raczej ok

potem to jakaś mieszanka no 1,2,4; 1,3,4 mniej więcej tak trzeba wytypować te 5 najmniejszych lub nieco inne podejście

chyba łatwiejsze z punktu implementacji ale na pewno bardziej zasobożerne: pierwsza liczba to będzie 29 bo 2*3*5=30; 30 -1 = 29

i teraz zaczynając od n =31 sprawdź czy liczba n-1 podzielona przez 3 różne liczby pierwsze da 1. Coś takiego.


(Pablo_Wawa) #4

1 i 4 to nie są liczby pierwsze.

Poza tym chodzi o liczbę 31 (pierwsza z szukanych), a nie 29.

Co do ogólności problemu (jeśli interesuje nas nie tylko 5 pierwszych, ale może i więcej liczb), to sugeruję lecieć po kolejnych liczbach od 30 i sprawdzać, czy ta dzieli się kolejno przez którąś z liczb pierwszych (wcześniej stablicowanych) - ważne, żeby lecąc po kolejnych liczbach pierwszych brać do dalszego dzielenia nie całą liczbę, a wynik dzielenia. Sprawdzać można do SQRT(n) (pierwiastek z liczby n). Trzecie dzielenie (bez reszty) powinno dać 1 - wtedy wypisujemy bazową liczbę (n+1). Algorytm może nie najefektywniejszy, ale prosty i szybki.


(Rolek0) #5

Chyba chodziło mu o indeksy. Tak przynajmniej mi się wydaje po ostatnim akapicie. :-k


([alex]) #6

2*3*5+1

2*3*7+1

2*5*7+1

i po sprawie.


(kostek135) #7

Pablo ma w większości rację, choć z jednym się nie zgodzę do końca.

  1. Pierwszą szukana liczba jest 31.

Generalnie należy zapisać wszystkie liczby pierwsze do pewnej wartości 2, 3, 5, 7, 11, 13, ...

  1. Z własności iloczynu wiemy, że pierwszą szukana liczbą będzie {2 * 3 * 5} + 1, przy czym w nawiasach wąsatych mamy nasze n - 1, stąd należy 1 dodać.

Lepszy algorytm będzie polegał na tym, że następnym iloczynem z braku wyboru będzie 2 * 3 * 7, następny 2 * 5 * 7 albo 2 * 3 * 11 wszystkie inne będą większe. Innymi słowy musimy zrobić 5 pointerów (albo indeksery). W ogólnym przypadku iloczyn naszej liczby składa się z a * b * c i ap, bp, cp wskazują na indeksy + 2 wskazujące na lower-bound w b i c. Sprawdzamy czy dałoby się przesunąć ap na następną pozycję jeśli nie ma pointera od b to patrzymy jaka liczbę dostaniemy w wyniku podmiany jednego z czynników, analogicznie dla b, a dla c po prostu next, bo nie ma blokady. Z tych 5 możliwości bierzemy min i przesuwamy odpowiedni pointer. Jeśli l-b zrówna się pointerem rozważamy tylko pointer (lower-bound nie może przekroczyć pointera). Przykładowo właśnie po 2 * 3 * 11, będzie 2 * 5 * 7, w sumie trochę pogmatwałem, jeśli autor potrzebuje mogę to wyspecyfikować w punktach.

-- Dodane 25.01.2013 (Pt) 18:14 --

@[alex]

Mylisz się trzecia będzie 2 * 3 * 11 + 1 = 67, u ciebie 71.


(lukasz_n) #8

@kostek135

Czy mógłbyś mi zgodnie z sugestią napisać w punktach Twój algorytm na rozwiązanie tego 'problemu'?

Na pewno będzie to łatwiejsze do zrozumienia dla mnie.

Z góry dziękuję.


([alex]) #9
#include 

#include 

using namespace std;


int main()

  {

   unsigned Tb[]={2,3,5,7,11,13};

   const unsigned TbSize=sizeof(Tb)/sizeof(*Tb);

   bool map[TbSize]={false};

   if(TbSize<3) cout<<"za malo liczb"<
   else

     {

      for(unsigned i=0;i<3;++i) map[i]=true;

      bool more=true;

      for(unsigned nr=1;more;++nr)

        {

         cout<
         unsigned v=1;

         for(unsigned i=0;i
           {

            if(map[i])

              {

               if(v>1) cout<<"*";

               cout<
               v*=Tb[i];

              }

           }

         cout<<"+1 = "<<(v+1)<
         more=false;

         for(unsigned i=1;i
           {

            if((!map[i])&&(map[i-1]))

              {

               map[i-1]=false;

               map[i]=more=true;

               break;

              }

           }

        }      

     }   

   return 0;

  }

(lukasz_n) #10

@[alex]

Dziękuję bardzo za kod, wiele wyjaśnia i we wspaniały sposób pokazuje rozwiązanie postawionego problemu.

Dziękuję i pozdrawiam

Łukasz