Kod prvocisla – Java – Fórum – Programujte.com

Připojen obrázek.Ahoj, v tom druhem cyklu For, to j++ ,neni to tam vcelku k nicemu. Z prvniho cyklu se dosadi hodnota cisla a v druhem cyklu se podeli 2ma a upresni se Modulem,zda je cislo delitelne jinou hodnotou nez samo sebou. Chapu to dobre? Dekuji

Nevím, co myslíš tím, že se podělí dvěma a upřesní modulem.

Modulo je zbytek po celočíselném dělení. Takže to zkouší jestli hodnota `i` je beze zbytku dělitelná hodnotou `j`. A zkouší to pro všechna `j` od 2 do i/j. Takže j++ tam samozřejmě má smysl.

Vratim se tedy k druhemu cyklu, pokud z prvniho cyklu obdržím např. hodnotu 6, tak dosadím( j=2; 2<=6/2;j++;) to znamena,ze je splnena podminka v druhem cyklu "For" a pokracuje se do "if" podminky. Co se deje pak s "j++"v druhem cyklu FOR, zvetsi se na hodnotu 3 a pak ( j=3; 3<=6/3;j++;) a pak ..konec ..., protoze 2 neni vetsi nez 3 nebo...??? Tohle mi dela problem nebo se pak uz prejde do prvniho "For" cyklu ?? Dekuji

Má hledat prvočísla v rozsahu 2 až 100. První cyklus prochází tento rozsah (tj. 2, 3, 4, .... 99, 100), číslo se jmenuje i. Uvnitř tohoto cyklu se zjišťuje, zda je to prvočíslo. Hrubou silou by se to udělalo tak, že by otrocky podělil číslo i každým číslem z rozsahu 2 až i-1, číslo kterým dělí se jmenuje j. Ukončovací podmínka j <= i/j podle mého názoru zmenší počet iterací cyklu, protože nemá smysl zkoušet všechna čísla z rozsahu 2 až i-1. Koneckonců 6 není dělitelné č. 5.

Algoritmus zjišťuje, zda je číslo dělitelné jiným číslem. Pokud ano, modulo vrátí 0, pak je i dělitelné číslem j. Takže pokud uvnitř druhého cyklu vrátí modulo alespoň jednou 0, našel dalšího dělitele, a číslo není prvočíslo.

Pro případ č 6 vnitřní cyklus:
1. i = 6, j = 2.  Podmínka j <= i/j vrátí true, protože i/j je 3. Následně i % j vrátí 0 a podmínka uvnitř druhého cyklu vrací true a proměnnou je prvocislo nastaví na false. v tuto chvíli už nemá smysl dále zkoumat číslo i, je jasné, že není prvočíslo.
2. i = 6, j = 3.  Podmínka j <= i/j vrátí false, další iterace vnitřního cyklu neproběhne. Ani není nutná, že 6 není prvočíslo už víme.
3. výpis neprohěhne, proměnná jeprvocislo == false

Následuje další iterace vnějšího cyklu, kde i = 7 a opět se ve vnitřním cyklu zjišťuje, zda existuje další dělitel. Tentokrát v každé iteraci (asi bude opět jedna) vnitřního cyklu modulo vrátí nenulové číslo.

hu

Pozn.: zkus si to pro větší čísla, např 29, 30, 31. Pro ty bude více iterací vnitřního cyklu

hu

Pokud jde konkrétně o to "i/j", tak to je nesmysl. Nebo ono to teda "nakonec zafunguje", ale je nesmyl to formulovat takhle.

Mohl bys to matematicky zdůvodnit? A předložit podle tebe správné řešení?

hu

Jede to dokud je "j <= i/j". Nebo naopak: skončí to, když "j*j > i". Takže limit pro `j` je druhá odmocnina `i`. Proč to tak nenapsat rovnou?

#8 gna
Druhá mocnina i tam nemá co hledat. Špatně jsi tu nerovnost upravil. Pokud nerovnost vynásobíme číslem j, pak dostaneme j*j <= i, tedy druhá mocnina j menší rovna i. V původní nerovnosti j nesmí být nula a tak násobení číslem j lze provést.

Možná existuje nějaká definice, která říká, že limit je pro takové j, které je menší rovno podílu i/j. Pak je jen otázka, zda má smysl upravit na j*j <= i, ono to na efektivitu nemusí mít vliv, ale dokonale to zakryje "původ" ukončovací podmínky.

Násobení vs dělení: dodnes používám 8051, která už od počátku měla instrukce MUL AB a DIV AB. Obě dokázala vykonat za 2 strojové cykly, takže tam nemohli šaškovat se složitým počítáním nějakým mikroprogramem (kdo ví, jestli něco takového znali). Zatímco násobení jsem viděl popsané jako kombinační logickou funkci, u dělení se pouze domnívám, že taková kombinační logická funkce existuje. Z toho usuzuji, že úprava výrazu na násobení efektivitu pravděpodobně nepřinese.

31 let po maturitě se toho hodně zapomene a existenci definice jsem neověřoval.

hu

Chtěl jsi to matematicky zdůvodnit. Neříkám, že to má přepsat na násobení, jen jsem na tom ukázal, že ten limit je druhá odmocnina. Na tom není co řešit.

Žádná definice s i/j neexistuje. Je to neintuitivní způsob, jak nakonec narazit na tu odmocninu. Představ si to pro číslo 100: 

2 <= 50
3 <= 33
4 <= 25
...
10 <= 10
konec

Bum:

for (j = 2; j <= sqrt(i); j++)

Zatím to spíš vypadalo, že neumíš upravovat nerovnice.

Pokud bych si měl vybrat, tak bych raději použil celočíselné dělení. Navíc je následováno modulo, tedy zbytkem po celočíselném dělení. Po zkušenostech s algebrou na jednočipech se mi to jeví efektivnější než odmocnina a pak modulo (zřejmě se při něm spočítá i podíl, ale nevyužitý se zahodí).

hu

Neříkám, že tam má být odmocňování. Jen vysvětluju, co to dělá.

A protože je evidentně strašný problém to pochopit, tak je nesmysl to dělat takhle "krypticky".

Tak ukaž lepší řešení.

hu

Mně nějak nenapadá, jak jasně vyjádřit, že to zkouší jen čísla do odmocniny...   

#14 gna
Podělím čísla a pokud je podíl menší než dělitel, končím.

#15 Kit
Já jsem to myslel ironicky   

je nesmysl to dělat takhle "krypticky".

Rozumím tomu tak, že to dělají špatně. Pořád čekám, že ukážeš lepší řešení.

Ve vláknu jsem pokračoval v naději, že se něco nového naučím. Moje očekávání jsi nenaplnil ani z části.

hu

Mě nejdříve ani nenapadlo, že by v tom "i/j" mohl být problém, i když i já jsem se nad tím musel zamyslet. Až z dalších komentářů mi došlo, že právě v tom asi je kámen úrazu.

Tak jsem matematicky i empricky osvětlil, co to dělá. Projde to `j` od 2 do odmocniny `i`. Tečka. Podle tebe jasná forma zakrývá význam nejasné formy, neumím upravovat nerovnice a jakásí ptákovina s nulou. OK

Nikomu necpu, že to musí být jinak, ale podlě mě je nesmysl psát neintuitivně, když to jde napsat jasně. Nejjasnější vyjádření odmocniny je odmocnina. 

for (j = 2; j <= sqrt(i); j++)

Samozřejmě je odmocnina výpočetně náročnější, ale stačí ji spočítat jen jednou a celý ten algoritmus může být efektivnější a blabla, ale o to původnímu autorovi zjevně nešlo, když se neobtežoval ani s breakem při zjištění výsledku.

jakásí ptákovina s nulou

jestli narážíš na to, jak jsem zdůvodnil násobení číslem j při odstranění zlomku na pravé straně nerovnosti, tak ta ptákovina je z učebnice matematiky.

Samozřejmě je odmocnina výpočetně náročnější, ale stačí ji spočítat jen jednou a celý ten algoritmus může být efektivnější

možná ano.

S tím break při zjištění, že není prvočíslo, mne to napadlo taky. Vypadá to jako školní úloha a autorovi zřejmě nešlo o efektivitu, ale o známku.

Pokud si dobře vzpomínám, tak jsem školní úlohy dělal nerad, Jejich vyhotovení jsem odkládal (někdy až po rychlé opsání řešení o přestávce) a když už jsem se do toho dal, snažil jsem se mít co nejdřív hotovo. Takže žádný hon za efektivitou. "Vypadá to, že to funguje, tím pro mne práce na domácí úloze končí a jdu dělat něco, co mne baví." Dnešní studenti to asi nemají jinak. Jen těch možností opisovat mají trochu více, za nás nebyl internet.

hu

Jen ještě taková drobnost. Java umí DivMod a jestli překladač postřehne, že může obě operace udělat jednou instrukcí, tak je řešení s dělením parádička.

#20 gna
DivMod umí i samotný procesor. Pokud chytřejší kompilátor narazí na instrukce div a mod blízko sebe, tak je sloučí.

Ahoj - zde je má varianta. Prosím o posouzení zda na to nejdu zbytečně moc složitě? 

public class ClassPrvocislo {

    //Napište program který najde všechny prvočísla mezi 2 a 100
    public static void main(String[] args) {

        int o = 2; //rozsah od
        int d = 100; //rozsah do
        int[] p = new int[d + 1]; //inicializace pole čísel v požadovaném rozsahu
        for (int j = 0; j < p.length; j++) { //naplnění pole čísly
            p[j] = j;
        }

        for (int i = o; i < p.length; i++) {
            if (p[i] != 0) {
                for (int j = i; j < p.length; j++) {
                    if ((p[j] != 0) && (i != j) && (j % i == 0)) {
                        p[j] = 0;
                    }
                }
                System.out.print(p[i] + ", "); //výpis prvočísel v daném rozsahu
            }
        }

    }
}

To je otázka, co je moc složité. Jednodušší řešení máš tady nahoře, ale to tvoje bych řekl, že je přímočaré řešení bez překvápek a v tomhle smyslu u mě vpoho.

Akorát u toho nulovacího cyklu je trochu nesmysl ty násobky "hledat", když můžeš jít přímo po nich. Ale to je jen drobnost.

for (int j = i + i; j < p.length; j += i)
    p[j] = 0;

#23 gna
No vidíš to mě vůbec nenapadlo jít přímo po násobcích. Díky za dobrý postřech. 

#24 Z_code
Díky