Kontajner, ktory.... – C / C++ – Fórum – Programujte.com

ahoj,
potreboval by som kontajner, ktory vie najst prvky podla hodnoty(nie indexu), resp. mazat ich podla moznosti v O(1)...

totiz potrebujem zistim prvocisla v nejakom rozsahu(napr. 1 az 10 000 000) a napadlo ma, ze to spravim cez eratostenovo sito(vsetky cisla supnem tu a potom mazem nasobky...) any better ideas? :)

nevim ale prijde mi ze na to jdes moc slozite, nebylo by lepsi v cyklu o poctu iteraci odpovidajici rozsahu kontrolovat delitelnost iterovane promenne jiz nalezenymi prvocisly, ktera bys ukladal do nejakeho treba vektoru? (pozn: iterace by ti stacila po dvou)

v nasich skriptach na c mame hladanie prvocisla podla erastenovho sita... kod ti mozem poskytnut

Nebo si ho muze snadno najit... uz treba i na ty pitomy wikipedii...

a nebo ho hlavne muze sam zkusit napsat bez cumeni na nejakej hotovej zdrojak jen na zaklade ty myslenky. opisovanim cizych zdrojaku se nikdy programovat nenauci

Co treba pole o tom rozsahu a jednotlive polozky 0/1 smazano.

huha, tych answerov ale je ;)
takze pekne po jednom:
tmi(prvy tvoj post): noo imho tvoje je skor zlozitejsie a hlavne casovo o dost narocnejsie, resp. ked som dobre pochopil, tak si mal na mysli nieco take ako

for(int i=0; i != range_end; i+=2){/*rozhodnem, ci je to prvocislo*/}

hele myslis si ze to de v lepsim case nez to mam? abych se priznal, moje znalosti vlastnosti prvocisel jsou mizive (vicemene konci u bertrandova postulatu), ale myslim si ze nemuzes (alespon o tom nevim) obecne spocitat pocet prvocisel v nejakem rozsahu lepe nez jejim vyctem.
k cemu chces tady pouzivat binarni hledani? to mi nedochazi... jestlize chces znat pocet prvocisel v urcitem intervalu, pak (pokud uz ta prvocisla dopredu neznas, ale to by pak ten program trochu nemel smysl) tak si je proste do onoho intervalu dogenerujes a spocitas.

btw. sice ti to zkraceni casu na polovinu vynechanim sudych cisel nepomuze, ale dava to najevo ze tusis o co jde.

ohledne te slozitosti: pokud umis rozhodnout v konst. case zdali je cislo prvocislo, pak ma muj alg. slozitost O(N). ja to tedy neumim, takze ta slozitost je "trochu vetsi", konkretne O(N*log(log N)) pri pouziti ersita. o kterem si koneckoncu mluvil i ty, tak nevim proc by mel byt tvuj alg lepsi nez muj.

tmi: okay, okay, neratal som zlozitost ersita takze nemozem sa s tebou hadat :) kazdopadne som si nevsimol, ze tiez pouzivas ersito pri tvojom rieseni;)

a k comu pouzivat to binarne hladanie? nechce sa mi kazdy detail zadania opisovat, tak radsej tu supnem cele ;)

Časový limit: 50s

Pamäťový limit: 32MB



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 ≤ 20) – počet intervalov, ktoré budú nasledovať. Nasleduje T riadkov, v i-tom z nich sú 2 celé čísla ai, bi (1 ≤ ai ≤ bi ≤ 1 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).

Poznámky

Prvočíslo je prirodzené číslo, ktoré má práve dvoch deliteľov (jednotku a seba samého). Najmenšie prvočísla sú teda 2, 3, 5, 7, 11, ...

Snaž sa, aby tvoj program bol čo najrýchlejší. Nerátaj zbytočne viackrát to isté. Zbytočne pomalé programy nemusia stihnúť skončiť v časovom limite.

Príklad

Vstup

3

3 5

122 125

340000 350000

Výstup

2

0

795

Přez to sito se na to vykašli. Taky jednou mi kamarád řekl ať vypíšu prvočísla v nějakým rozsahu, já jsem neznal algoritmus, ale pak mi poradil a už jsem to napsal:
Dokázal jsme ten kod tak kratce zapsat že ho mám i v javě.

C++

	bool JePrvocislo(int cislo)

	{

		if (cislo == 0) return false; // vyjimka

		for (int i = (int)sqrt(cislo); i != 1; --i)

			if ((cislo % i) == 0)

				return false;

		return true;

	}

	static boolean JePrvocislo(int cislo)

	{

		if (cislo == 0) return false; // vyjimka

		for (int i = (int)Math.sqrt(cislo); i != 1; --i)

			if ((cislo % i) == 0)

				return false;

		return true;

	}

Vysvětlení:
Ještě bych vysvětlil ten algoritmus. Prvočíslo má jenom 2 dělitele jednim je 1 a druhym je číslo samotné. Když vemu číslo 25 tak k tomu abych zjistil zda to je prvočíslo nemusim kontrolovat od jedné do 25 jestli je dělitelné pouze 2x, stačí ho kontrolovat do 5 což je jeho odmocnina. To platí u každého čísla, když je tedy jeho odmoznina dělitelná do jedničky nějakym číslem je není to prvočíslo.
Proto ten algoritmus.
Podrobný rozbor algoritmu:
0 pokud si ze školy pamatuju správně neni prvočíslo ani neprvočíslo, ale patří do specialní skupiny, navíc s ní nelze dělit, tak musí být odchycena před testováním.
Proč ten for takto

for (int i = (int)Math.sqrt(cislo); i != 1; --i)

for (int i = 1 ; i != (int)Math.sqrt(cislo); i++)

noo je tu taky problemik; vid zadanie, ktore som poslal; totiz vstup bude urcite OBROVSKY(dostanem 1000 intervalov a v kazdom obrovskom rozsahu mam zistit pocet prvocisel, takze nemozem si dovolit to dvakrat pocitat). len tak zo srandy som narychlo nakodil ten priklad pomocou tej funkcie a este som tam pridal pre rychlost konktrolu, ze ak je cislo parne a je vacsie ako 2, tak to nieje prvocislo... noo skoncilo to obrovskym(kamarat nespecifikoval, akym) prekrocenim casoveho limitu

Tom@sQo:
No tak samozřejně algoritmus se dá vylepšovat na úkor přehlednosti. Tak ho vychytáme společně tady na foru. Takže tedka ho máš nějak talke?

bool JePrvocislo(int cislo)

{

    if ((cislo != 0) || ((cislo > 2)&&(cislo % 2 != 0))) 

		for (int i = (int)sqrt((double)cislo); i != 1; --i)

			if ((cislo % i) == 0)

				return false;

    return true;

}

#include <iostream>

#include <math.h>

#include <time.h>



using namespace std;



bool JePrvocislo(int cislo)

{

    if ((cislo != 0) || ((cislo > 2)&&(cislo % 2 != 0))) 

		for (int i = (int)sqrt((double)cislo); i != 1; --i)

			if ((cislo % i) == 0)

				return false;

    return true;

}





int main()

{

	clock_t start = clock(), end;

	for(int i = 1; i != 100000; ++i)

		if(JePrvocislo(i))

			cout<<i<<endl;

	end = clock();

	cout<< "Cas : "<< end - start ; 



	cin.get();

	return 0;

}

Upřesnění:
Tu smyčku bzrdí nevíce příkay cout.
Když tedy main upravim takto:

int main()

{

	clock_t start = clock();

	for(int i = 1; i != 100000; ++i)

		JePrvocislo(i);

	cout<< "Cas : "<< clock() - start;



	cin.get();

	return 0;

}

bool JePrvocislo(int cislo)

{

    if (cislo != 0) 

		for (int i = (int)sqrt((double)cislo); i != 1; --i)

			if ((cislo % i) == 0)

				return false;

    return true;

}

ahoj ;)
noo som sa sekol kusa aj ja, aj ty :)
1) tie prvocisla su v rozsahu od 1 do 1000000 vratane (ty si sa sekol), ale aj tak mi to zbehne do 7 sekund ;)
2) ten vstup bude maximalne to, ze: bude 20 hladani a ze casovo najnarocnejsi bude, ze najdi mi pocet prvocisel od 1 do 1000000(ja som sa sekol, bo som neprecital zadanie) a to musi stihnut do 50 sekund... kazdopadne cele to ukladam to vektoru a uz len naimplementujem binarne hladanie(co ***prosim vsetkych***, nepiste ho tu, ja ho chcem napisat sam :-] v utorok je deadline, takze dovtedy ho napisem ja sam ;-])

kazdopadne diky za ten algoritmus ;) vobec som si nemyslel, ze je taky rychly(len 7 sekund) pricom je ovela kratsi ako ersito ;-)

ps: miesto tej fcie clock, ti navrhujem pouzivat radsej moju formulku ;) "g++ -Wall subor.cpp; time ./a.out < in " ktoru velmi casto pouzivam na sutaziach na meranie casu ;-) a nepotrebujem tym spinit kod :)

Jj, já to nepsal podle zadání, ale abych ti poradil algoritmus. :smile1: To měření času moc nepoužívám, ale díky za tu ulitu na měření. Ono zase ve většim projektu kde se ti hodí čas jenotlivejch funkcí to už si kod zašpinit musíš s tim že to tam máš jenom když to ladíš a pak to smažeš..

Tak hodně štěstí a vyhraj ! ! ! :smile7: :smile7:

ja len pridam taky napad:
netreba deliť všetkymi čislami, stači deliť prvočislami menšimi ako odmocnina z kontrolovaneho čisla ;)

dnes je k dispozícii veľmi veľa pamäte, tak prečo nesptaviť 1MB subor s predvypočítanými číslami ? :)

cout << je pomalší ako printf() , mam to vyskušane.

mephi:
k tomu napadu: Tomas Dejmek to uz tak pouzil v kode ;)

daleeej co sa tyka toho 1MB suboru:
uz som to skusal hned prvy den, lenze mi to neprijalo...kod musi byt do 64 kB ale aj tak...limit je 50 sekund, z toho 7 sekund zaberie to generovanie, takze imho to ani netreba ukladat ;)

co sa tyka cout vs printf, tak je to pravda, ze cout je cca 15 krat pomalsi, lebo tam uz ta trieda je riadne premakana a dost ti dobre "detekuje" typy a (skoro) vsetko vypise spravne narozdiel od printf, kde musis typ explicitne uviest ;)
LENZE na sutaziach z programovania su ulohy naschval tak napisane, aby neslo o tieto blbosti, ale o casovu narocnost algoritmu... aj tu si uvedom, ze tych 20 riadkov vstupu vystupu je skoro uplne jedno, cim sa to vypise ;)

Tomas Dejmek:
diky za povzbudenie ;) podla http://kruzok.d42.sk/sutaz/index.php?act=results som az druhy(Tomas Novella), ale dufam, ze sa tvoje prianie splni ;))

memphi to myslel jinak, odmocnina je horní hranice z které zkoušíš dělit po jedničkách každou možnost (algoritmus odemě), on myslel dělit to pouze prvočísly, a má pravdu, ale nevim jestli to má cenu psát....
Vypadalo by to asi takle:
1) Vypočitání horní hranice testování ze vstupního čísla(ozmocnina).
2) vygenerování prvočísel do horní hranice.
3) testování zbytku po dělení prvočísly.

Bod 2 znamená zpomalujicí smyčku, ale bod 3 se tím zrychlí. Bod 2 by se dal obejít tim, že by jsi měl už čísla vygenerovaný sám (tím myslel to 1MB)
Otázka je jestli se dá mluvit o algoritmu. :smile3: Možná by se to ještě na úkor přehlednosti ale dalo ještě vylepšit, přemýšlej otom kdyžtak.

Soutěž: Věřim ti, 1. nemám moc navrch.
PS: Tomášové jsem asi nejlepší programátoři :smile6: :smile6: :smile6: viz tabulka

Jo hele jak sjem ten algoritmus upravil naposled, tak v té verzi JE CHYBA!!! Když to je nula vráti to true což je blbost... já jsem tam měniil tu podmínku a nevšim jsem si toho.

jak bych to asi resil ja:
nacitane vstupy bych hazel do intervaloveho stromu, a zaroven bych mezi nimi nasel maximum.
pote bych spustil alogritmus na hledani vsech prvocisel (je jedno jestli se pouzije klasicke ersito s eliminaci nasobku nebo jeho varinata s delenim (to je totiz v podstate taky ersito, jen funguje trochu jinak), zalezi na tom jak rychle pocitac zvlada nasobeni oproti deleni. vzhledem k tomu ze to jsou cela cisla bych se asi vice klonil k druhe variante). pravdepodobne bych je ukladal do nejakyho pole vsechny, dalsi pocitani se tim celkem urychli. pri postupnym pocitani prvocisel bych pouze kontroloval spodni patra toho intervalovyho stromu a pokud by cislo bylo v intervalu tak bych zvysil pocet v ramci intervalu, pripadne bych se posunul o interval vyse.
no a nakonec bych pro jednotlive zadane intervaly spocital ktere casti intervaloveho stromu jim patri.
vyhodu to ma tu ze se vse potrebne pocita skutecne jen jednou. nad slozitosti se mi spekulovat nechce (zalezi na tom jak by se implementoval ten intervalak), ono hledani prvocisel by trvalo onech O(n*log(logN)), kde N je nejvetsi cislo z intervalu. vytvoreni intervalaku by zalezelo na tom jak moc "disjunktivni" ty intervaly jsou, v nejlepsim logT, obecne asi O(log(pocet disjunktivnich podintervalu)), samotne spocitani by se zvladlo O(pocet_disjunktivnich_intervalu + pocet_prvocisel_v_0-N) a vypsani vysledku v O(pocet_disjunktivnich_podintervalu + T*log(pocet_disjunktivnich_podintervalu). Celkem to dava O (T*log(pocet_disjunktivnich_podintervalu) + pocet_disjunktivnich_podintervalu + pocet_prvocisel_v_0-N + N*log(logN)).
pametove je potreba O(pocet_prvocisel_v_0-N + pocet_disjunktnivnich_podintervalu).

tohle reseni by bylo efektivni jen pro hodne pruniku mezi zadanymi intervaly, pokud by tam zadne pruniky nebyly tak je celkem zbytecne ten intervalak stavet, pak by se totiz kazde prvocislo pocitalo jednou tak jako tak.