PCTuning fórum

Pěkně prosím , nezvládl by někdo naprogramovat v JAVĚ Eratostenovo síto - hledání prvočísel, prý je to jednoduché, ale na mě to je moc

Vysvětlení co to Eratostenovo síto je
http://paashi.wz.cz/prog_eratostenes.htm

Chápu myšlenku toho síta, ale nechápu jak to naprogramovat

Dark100 píše:Pěkně prosím :), nezvládl by někdo naprogramovat v JAVĚ Eratostenovo síto - hledání prvočísel, prý je to jednoduché, ale na mě to je moc :)

Vysvětlení co to Eratostenovo síto je
http://paashi.wz.cz/prog_eratostenes.htm

Chápu myšlenku toho síta, ale nechápu jak to naprogramovat :(

Nechapu, vzdyt je na ty strance reseni, akorat neni v jave... To je tak tezky to prepsat do javy?

No právě že je , zkusím na to pořádně přes víkend sednout ale moc si nevěřím

tak jak jsi dopadl o vikendu,zvladl jsi to?
jestli chces pomoc,tak se ozvi,uz jsem to jednou delal

no, když víš, jak to funguje, tak to snad neni problém vyrobit, ne? Vytvoříš bitový pole (typ bool) o velikosti rovnající se maximu, ze kterého chceš prvočísla hledat. Nastavíš všechny prvky pole na TRUE (= "je prvočíslo), nastavíš pole[0] a pole[1] na FALSE (0 a 1 nejsou prvočísla) a potom pomocí FOR cyklu procházíš pole (tj. od pole[2] a dál), pokud je daný prvek TRUE, pustíš druhý FOR cyklus, který nastaví všechny násobky daného indexu na FALSE ... takhle projdeš celé pole a všechny prvky, které budou mít TRUE jsou prvočísla. Zkrátka index v tom bitovym poli reprezentuje číslo.

Příklad: (sice jsem v Javě dělal naposled asi před rokem, ale na tohle neni nic xtra potřeba)

int delka = 1000; // maximum
bool pole[delka]; // nove pole
for(int a =0; a < delka; a++){ pole[a] = true; } // naplneni pole TRUE
pole[0] = false; pole[1] = false;
for(int a = 2; a < delka; a++) // pruchod pole od dvojky
{
/*kdyz je pole[a] aktivni (= a je prvocislo), vypni vsechny jeho nasobky*/
if(pole[a])
{
for(int b = 2*a; b < delka; b+=a)
{
pole = false;
}
}
}
// ted vsechny prvky pole, ktere jsou true, jsou prvocisla. Staci projit
// smyckou a vypsat nebo cokoli s tim chces udelat