problém : eratostenovo sito

[caparzo82999]

Zdravím, mám problém
ako vytvoriť eratostenovo sito, bez pouzitia 2 forov?? s 2 forami to mam, ale potrebujem s 1 forom, aby mi to nepadlo na timelimite, timelimit je 10 sekund a potrebujem sito az po 10 000 000

je to uloha na dynamicke programovanie, mate niekto nejaky napad, skusenosti??

vopred diky za odpoved

[galen]

idea:
spravis datovu strukturu, ktora obsahuje:
1) integer - cislo
2) pointer - na dalsiu takuto strukturu
3) pointer - na predchadzajucu takuto strukturu
4) boolean - flag, ci je prvocislo

krok cislo 1:
vytvoris dynamicke pole, naplnis strukturu...
zapamatas si "prvy element"
posledny prepojis na prvy (urobis kruh)

inicializacia: "prvy element" nastavis na "prvocislo"
nastavis pointer na "aktualne prvocislo" na "prvy element"
"aktualny element" nastavis na nasledovnika "prvy element"

Loop:
ak nieje "prvocislo":
{
"aktualny element" predel "aktualne prvocislo" a zisti, ci je nasobok, ak je nasobok, odstran ho zo struktury
jeho nasledovnik sa stane "aktualny element"
}
else // je prvocislo, tzn dokoncil sa kruh, si na zaciatku, a treba najst prve cislo, ktore nieje "prvocislo"
{
...
}
end Loop;


hadam si ten moj chaoticky popis pochopil... je pokrocila doba, netreba cakat zazraky

[RP]

Alebo rovno hotove riesenia na studium : http://badcomputer.org/unix/code/eratosthenes.bot" onclick="window.open(this.href);return false;

[pEpinko]

Prepisat 2 for cykly na jeden sa v niektorych jazykoch da uplne jednoducho, neviem ale ako ti to pomoze. Predpokladam, ze ty by si skor potreboval rychlejsi kod. Cize by som chybu hladal niekde inde ako v dvoch cykloch.

Skusil som to naprogramovat (aspon sa trochu precvicim) a bezi to ledva 1 sekundu. Cize 10sekund je az az.

EDIT: RP myslim ze sa mu viac zide to vymysliet samemu ako citat hotovy kod...

[caparzo82999]

diky za odpovede, ale ide o to, ze treba urobit sito z 10 000 000 cisel, vybrat vsetky prvocisla z urciteho intervalu a urcit ich pocet
pri 2 foroch to bude O(n^2), co pri 10 000 000 cisel do 10s nezbehne
osobne mi to funguje s 2 forami, ale je to pomale

skopirujem tu zadanie

Kód: Vybrať všetko

Počet prvočísel

Rasťo sa prednedávnom v jednej knižke dočítal, že prvočísel je nekonečne veľa… ale už o dve strany neskôr sa dozvedel aj to, že existujú ľubovoľne dlhé úseky po sebe idúcich prirodzených čísel, medzi ktorými nie je ani jedno prvočíslo. A ked na dôvažok zistil, že Bertrandov postulát hovorí, že pre každé N je medzi N a 2N aspoň jedno prvočíslo, mal v tom už dokonalý zmätok. Pomohol by mu program, ktorý by vedel pre zadané intervaly hovoriť, koľko prvočísel vlastne obsahujú.
Vstup

Na prvom riadku vstupu je jedno celé číslo T (1 ≤ T ≤ 100 000) – počet intervalov, ktoré budú nasledovať.
Nasleduje T riadkov, v i-tom z nich sú 2 celé čísla ai, bi (1 ≤ ai ≤ bi ≤ 10 000 000).
Výstup

Výstup by mal obsahovať T riadkov, na i-tom z nich jedno celé číslo – počet prvočísel, ktoré ležia medzi ai a bi (vrátane).
Príklad
Vstup
3
3 5
122 125
340000 350000
Výstup
2
0
795

moje pomale riesenie v jave

Kód: Vybrať všetko

package počet_prvočísel;

import java.util.Scanner;

public class Main {
	
	static boolean[] eratostenovoSito = new boolean[10000000];
	
	static boolean[] zistiPrvocisla(int d) {
		boolean cislo[] = new boolean[d+1];
		cislo[1] = true;
		
		for (int i = 2; i < d+1; i++) {
			if (cislo[i] == false) {
				for (int j = i*2; j < d+1; j += i) {
					cislo[j] = true;
				}
			}
		}
		return cislo;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		eratostenovoSito = zistiPrvocisla(10000000);
		
		int pocetIntervalov = sc.nextInt();
		sc.nextLine();
		
		for (int i = 0; i < pocetIntervalov; i++) {
			int vysledok = 0;
			int a = sc.nextInt();
			int b = sc.nextInt();
			sc.nextLine();
			
			for (int j = a; j <= b; j++) {
				if (!eratostenovoSito[j]) {
					vysledok++;
				}
			}
			System.out.println(vysledok);
		}
	}
}

[pEpinko]

Namiesto odstranenia druheho for cyklu (co ten algoritmus nijak nespravi linearnym). By som skusil upravit tuto pasaz:

for (int i = 2; (i * i) < d+1; i++) {
if (cislo == false) {
for (int j = i*2; j < d+1; j += i) {
cislo[j] = true;
}
}
}

[galen]

okej, budme megalomani...
0) sprav subor/datovu strukturu, ktora obsahuje vsetky prvocisla v rozsahu 1-10M
1) nacitaj tuto strukturu pri starte programu
2) nasledne zlozitostou o(n) vypises vsetky prvocisla mensie ako T

Zarucene to bude pod 10s

[caparzo82999]

aj po tejto uprave to hodilo timelimit

[pEpinko]

Moj kod v C:

Kód: Vybrať všetko

#include stdio.h
#include stdlib.h
#include time.h

#define SIZE 10000000

int main()
{
    int *arr = malloc(sizeof(int)*SIZE);
    int i;
    for (i = 0; i < SIZE; i++)
        arr[i] = i;
    int t = time(0);
    for (i = 2; i * i < SIZE; i++)
    {
        if (arr[i] != -1)
        {
            int n = 2;
            while ((i * n) < SIZE)
            {
                arr[i * n] = -1;
                n++;
            }
        }
    }
    t = time(0) - t;
    printf("Time: %i \n", t);
    free(arr);

    printf("Done.\n");
    return 0;
}

Bezi v podstate bez zdrzania. Neverim, ze Java by bola 10 krat pomalsia.

[wedro]

Bezi v podstate bez zdrzania. Neverim, ze Java by bola 10 krat pomalsia.

tomu ver!!! a este viac

k algoritmu:
najradsej by som použil list aby som vymazal cisla ktore niesu prvocisla a dalej ich nekontroloval.
a este da sa zobrat dalsie nevymazane cislo zo zoznamu ako nasobok aby som nemazal vzdy od nasobku 2, ktory tam aj tak uz neje, ale zacat mazat od dalsieho.
no a lepsie asi vypocitat vsetky prvocisla z intervalu lebo 100 000 krat testovat sa asi neoplati.

ale aj tak ti to nezbehne za 5!!! sekund ( ano je tam limit 5 a ne 10) kolega!!! muhuhahaha
PS: tebe ucho!!!

[galen]

Bezi v podstate bez zdrzania. Neverim, ze Java by bola 10 krat pomalsia.

tomu ver!!! a este viac

no daj este daky vtip

k algoritmu:
najradsej by som použil list aby som vymazal cisla ktore niesu prvocisla a dalej ich nekontroloval.

spravna uvaha, ale potom je problem v prechadzani na kazdy druhy, treti, Nty (kde N je prvocislo) zaznam Listu, tak aby to bolo ako nasobok, nie N-ty zaznam v Liste

a este da sa zobrat dalsie nevymazane cislo zo zoznamu ako nasobok aby som nemazal vzdy od nasobku 2, ktory tam aj tak uz neje, ale zacat mazat od dalsieho.

Inicializacia pola s polovicnou pocetnostou je dobra idea , da sa usetrit par krokov

no a lepsie asi vypocitat vsetky prvocisla z intervalu lebo 100 000 krat testovat sa asi neoplati.

Ono, najefektivnejsie by bolo asi spravit pole o 10M zaznamoch, kde kazdy zaznam by mal pocet prvocisiel pred nim,
po skonceni inicializacie, by si uzivatel zadal svoje poziadavky, a narocnost zistenia spravnych poctov od zadania poziadavky by bola O(1), nie O(n), nieto este O(n*n),
treba vsak ratat s tym, ako dlho by trvala inicializacia tohto pola. v kazdom pripade to nespada do kategorie "odozva od zadania" takze to moze trvat aj dni...

ale aj tak ti to nezbehne za 5!!! sekund ( ano je tam limit 5 a ne 10) kolega!!! muhuhahaha
PS: tebe ucho!!!

zadanie tak ako je, ma doraz na optimalizaciu riesenia. realny cas, za ktory to zbehne by som neriesil.
ak sa to spusti na 286ke, tak to za 10s nespracuje ani 10 000 zaznamov, nieto este miliony ...
tu uz fakt nakluse konkretny procacik s lopatickou do prvej linie, a zacne makat ako velky ...

[wedro]

Bezi v podstate bez zdrzania. Neverim, ze Java by bola 10 krat pomalsia.

tomu ver!!! a este viac

no daj este daky vtip

och jaj, si to porovnaval že baviš mudreho?
-java ma pomale načitavanie zo scannera a pri 100 000 sadach vstupov sa to prejavy

a k tomu nasobku:(musim polopate lebo dakomu nedochadza)
takze mame pole cisel, zoberieme dvojku a vymazeme vsetky nasobky dvojky... ostane 2,3,5,7,9,...
zoberem trojku a vymazem 3.nasobok, 5.nasobok, 7.nasobok,...
zoberem patku a vymazem 5.nasobok, 7.nasobok, 11.nasobok,...
atd. comprende?

[pEpinko]

-java ma pomale načitavanie zo scannera a pri 100 000 sadach vstupov sa to prejavy

Tak toto asi uplne meni podstatu problemu. Ak je tych testovacich dvojic 100 000, tak potom jednoznacne treba urobit to co pisal galen, teda vytvorit pole o 10M prvkov, nechat tam len prvocisla (ostatnym mozme dat 0) pomocou toho sita a potom ho znova cele prejst a premenit na typ: na i tom mieste si pamatam kolko je prvocisel pred cislom i (asi aj vratane). Kazdy dotaz na pocet prvociel medzi A, B by bol rieseny v konstantnom case.

A tomu ze java je pri takychto aritmetickych operaciach pomalsia 10 krat ako C sa da verit len tazko, nieje tam nic co by ju mohlo spomalit. Ale ako je na tom z rychlostou scanner neviem...

[faugusztin]

Bodaj by ho nespomalovalo, ked ta trieda Scanner je v podstate nadstavba nad regularnymi vyrazmi, ktore su uz z principu pomalsie ako normalne nacitavanie retazcov.

[galen]

och jaj, si to porovnaval že baviš mudreho?
-java ma pomale načitavanie zo scannera a pri 100 000 sadach vstupov sa to prejavy

ano, ale aspon sa mam o co opriet,
vsetko je otazkou JVMka, ktore dany procesor vyuziva, na mikromasinach, ako napriklad mixer, teplovzdusna rura, alebo mikrovlnka, je javacky program porovnatelne rychly (95-110% casovej narocnosti, ako nativny C programek), zatial co hlavna vyhoda javy je, ze pri zmene procaku na tom jednoucelovom zariadeni to netreba cele prerabat, ako Ccko ...

samozrejme, ked ides do grafiky, java sux. ale ked vykompilujes GUI pre winy, tazko ho spustis na niecom inom ... takze tam sa da povedat, ze to je sice pomale, ale aspon to chodi.

co sa tyka operacii s cislami, spytaj sa gugla, alebo si iba precitaj nasledovne http://www.idiom.com/~zilla/Computer/ja ... hmark.html.
Tolko ku flame Java vs C

.net nema zmysel porovnavat, lebo ten ide cez VMko tak isto, ako java, a o jeho "rychlosti" je zbytocne sa bavit

a k tomu nasobku:(musim polopate lebo dakomu nedochadza)
takze mame pole cisel, zoberieme dvojku a vymazeme vsetky nasobky dvojky... ostane 2,3,5,7,9,...
zoberem trojku a vymazem 3.nasobok, 5.nasobok, 7.nasobok,...
zoberem patku a vymazem 5.nasobok, 7.nasobok, 11.nasobok,...
atd. comprende?

asi som stale trubka, ale ako to chces robit ? do akej datovej struktury to chces dat? hashmapa ?
plus budme megalomani, spracuvavas cislo 100 000:
vezmes 2, 50 000x poodstranujes nasobok 2ky
vezmes 3, 33 333x poodstranujes nasobok 3ky
vezmes 5, 20 000x poodstranujes nasobok 5ky ?
...
prave si spravil viac ako 100 000 ukonov, aby si prisiel na to, ze odstranujes cisla, ktore uz si davno odstranil ...


skus navrhnut, ako by si pristupoval na "pretriedene" pole, pri zlozitosti o(1) ku prvku, ktory chces odstranit