Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Dijagram toka za Mersenove proste brojeve

[es] :: C/C++ programiranje :: C/C++ za početnike :: Dijagram toka za Mersenove proste brojeve

[ Pregleda: 1671 | Odgovora: 6 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

bubamara997
Keljalić Nejra
Banja Luka

Član broj: 332438
Poruke: 2
*.187.61.176.bhb.ba.



+1 Profil

icon Dijagram toka za Mersenove proste brojeve13.02.2016. u 11:51 - pre 49 meseci
Imam problem oko zadatka.. Molim pomoc ako moze..
Zadatak glasi:
Dijagramom toka predstaviti algoritam koji ucitava broj n, a zatim ispisuje prvih n Mersenovih prostih brojeva. Mersenovi prosti brojevi su prosti brojevi oblika 2^k-1, k>=2. Prirodan broj veci od jedan je prost ako je djeljiv samo sa jedan i samim sobom.

Znam da je zadatak lagan ali problem mi je nastao kod 2^k
 
Odgovor na temu

Rapaic Rajko
Bgd

Član broj: 4105
Poruke: 785
188.124.211.*



+61 Profil

icon Re: Dijagram toka za Mersenove proste brojeve15.02.2016. u 08:07 - pre 49 meseci
Evo neki hint, vezano za oblik 2^k - 1.

Posmatramo neki broj x; kako ustanoviti da li spada u trazenu grupu? Ja bih pokusao ovako. Dodam 1 (jedinicu) na x i dobijem x1, i zatim udjem u petlju:

Code:

  while ((x1 > 0) && (x1 % 2) == 0) // x1 je int, podrazumevano
    x1 >>= 1;                           // shift-ujemo ga u desno za 1 bit, ekvivalentan kod je: x1 = x1 / 2; 


Na izlazu iz petlje, ako je x1 = 0, tada je polazni broj x upravo oblika 2^k - 1. Da li je Mersenov broj, e to moras da proveris da li je i prost .

Pozz
 
Odgovor na temu

bubamara997
Keljalić Nejra
Banja Luka

Član broj: 332438
Poruke: 2
..ppoe.dyn.broadband.blic.net.



+1 Profil

icon Re: Dijagram toka za Mersenove proste brojeve17.02.2016. u 12:23 - pre 49 meseci
Hvala puno
 
Odgovor na temu

Rapaic Rajko
Bgd

Član broj: 4105
Poruke: 785
188.124.211.*



+61 Profil

icon Re: Dijagram toka za Mersenove proste brojeve17.02.2016. u 14:09 - pre 48 meseci
Uh... ne zahvaljuj prebrzo.

Sad sam uvideo gresku u uslovu petlje(na brzinu je radjeno), kod zapravo treba da ide ovako:

Code:

  while ((x1 > 1) && (x1 % 2) == 0)
    x1 >>= 1; 


Dakle, ako je na izlazu iz petlje x1 == 1, tada je polazni broj x trazenog oblika 2^k - 1. Jer za x1 == 1, nikad se nece pozvati x1 >>= 1 (zbog modulo uslova), i x1 nikad nece doseci 0 (nulu).

Pozz
 
Odgovor na temu

jablan

Član broj: 8286
Poruke: 4541



+708 Profil

icon Re: Dijagram toka za Mersenove proste brojeve17.02.2016. u 16:08 - pre 48 meseci
Da li je broj stepen broja 2 najlakše proveriti tako što mu prebrojiš 1 bitove. Ako ima jedan 1 bit, onda jeste, inače nije. :)

BTW nije li brže da se mersenovi brojevi traže tako što se redom proveravaju brojevi oblika 2^k-1 na prostoću, nego da se proveravaju redom prosti brojevi na to da li zadovoljavaju zadati oblik? :)
 
Odgovor na temu

scoolptor

Član broj: 305514
Poruke: 1091



+424 Profil

icon Re: Dijagram toka za Mersenove proste brojeve17.02.2016. u 16:28 - pre 48 meseci
Citat:
Da li je broj stepen broja 2 najlakše proveriti tako što mu prebrojiš 1 bitove


Jos je lakse da uradis bitwise I sa vrednoscu umanjenom za 1. Ukoliko je rezultat 0, radi se o stepenu broja dva.

Specijalni slucaj je vrednost 0.

Primer n = 16 = 0b10000

n & (n - 1) = 0b10000 & 0b1111 = 0

All we are saying, is give a piece of chance.
 
Odgovor na temu

Rapaic Rajko
Bgd

Član broj: 4105
Poruke: 785
188.124.211.*



+61 Profil

icon Re: Dijagram toka za Mersenove proste brojeve18.02.2016. u 07:35 - pre 48 meseci
Au, sjajno razmisljanje .

Medjutim, trazi se dijagram toka - pretpostavljam da se trazi nesto smisleno, a ne 'magic code' (mada, koristio sam '>>'). Sta kad bi trazeni oblik broja bio n^k - 1 (n umesto 2)?
Onda bi valjda donji kod radio (opet je int x1 = x + 1):

Code:

  while ((x1 > 1) && (x1 % n) == 0)
    x1 /= n;


Drzi li ovo vodu: ako je po izlasku iz petlje x1 == 1, pocetni x1 je stepen broja n?

Pozz


[Ovu poruku je menjao Rapaic Rajko dana 18.02.2016. u 13:30 GMT+1]

[Ovu poruku je menjao Rapaic Rajko dana 18.02.2016. u 13:30 GMT+1]
 
Odgovor na temu

[es] :: C/C++ programiranje :: C/C++ za početnike :: Dijagram toka za Mersenove proste brojeve

[ Pregleda: 1671 | Odgovora: 6 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.