Goldbach je muj nepritel prosim o pomoc – Pascal – Fórum – Programujte.com

Mam takoveto zadaní
Slavná Goldbachova hypotéza říká, že každé sudé číslo větší než dva se dá zapsat jako součet dvou (ne nutně různých) prvočísel. Dokázat se nám ji asi nepodaří, ale pojďme si ji aspoň vyzkoušet pro malá čísla.

Na standardním vstupu jsou zadána přirozená čísla (každé na samostatném řádku, ukončena nulou). Vypište pro každé z nich buďto řádek X=A+B, kde X je zadané číslo, a A a B jsou prvočísla se součtem X, nebo, pokud rozklad neexistuje, řádek s textem "Ouch!". Můžete předpokládat, že čísla na vstupu nepřekročí 1000000.

Aby byl výstup vašeho programu jednoznačný, vypište rozklad, v němž je A≤B a A je nejmenší možné.

Poznámka: Jednička není prvočíslo :-)

Příklad: Pro vstup:
4
6
8
11

je správný výsledek:
4=2+2
6=3+3
8=3+5
Ouch!


Neni problem napsat na toto program ja mam problem s casovou slozitosti mohl by mi nekdo poradit jak to napsat co nejefektivnejsi (nejrychlejsi. Dekuji za pomoc

spam je píča všichni jsou píča

Ahoj, nejsi náhodou v prváku na matfyzu? Že by úloha z programování?:-)

To Pepca :
Ahoj, náhodou, nevíš už, jak se to má napsat? Zkoušela jsem to, ale nedopadlo to zatím.
Přeju hodně úspěchů :o)

no tak vygeneruj si nejdriv prvocisla do nejakyho limitu pomoci eratosthenova sita
a pak muzes uz kombinovat ... jen je otazkou zda to delat jako kazdy s kazdym z toho vysitovanyho souboru prvocisel nebo brat ty sudy cisla a zkouset je davat dohromady... hadam ale ze kombinovat ty prvocisla bude rychlejsi...
pak asi ideal bude mit jeste pole ... a budes si znacit cisla (na dane pozici v poli jako ze maji soucet...)

neco jako: (prodpoklada se ale ze uz tam budou jen prvocisla... tj index 1)

for i:=1 to 1000 do
for j:=1 to 1000 do begin
sude[ (prvocisla[i]+prvocisla[j]) div 2 ] = 1 ; (* nebudem zbytecne plytvat pameti... liche cisla netreba *)
end;

a nakonec jen projedes vse... jo pocitat s tim ze maximalni index pole bude vlastne posledni prvocislo ktery mas v poli prvocisla...

urcite to usetri hodne 1) nemusis testovat ktery cislo je prvocislo.. mas to rovnou vygenerovany
2) nemusis brat ty sudy cisla a hledat ktery dve prvocisla k nim pasujou...

nevyhoda bude pokud budes chtit treba do 100000000 tak uz to ukousne skoro pul giga ram :)

To KIIV :
já bych to -něco jako- vylepšil možná takhle abychom boostovali...
for i:=1 to 1000 do
for j:=1000 downto i do begin
suma:=prvocisla[i]+prvocisla[j];
for k:=1 to vstupu do If vstup[k]=suma then ... {mame i+j, citadlo++}
If citadlo=vstupu then konec {nebude ouch}
end;

a ta 1000 se da udelat plovouci podle numera na vstupu

Já při prvním spuštění vygeneruju prvočísla a uložím je do souboru, ze kterého je pak při každém dalším spuštění načítám (místo generování). Běhá to bleskově :smile1:

To joe : jo to taky neni vubec blbej napad :D ... urcite me nekdy napad akorat sem se ubranil... :o) j/k

Ahoj, nemáte někdo napsaný ten program komplet? Zkouším, zkouším,...,nefunguje :-(
Pomóc prosím

zkousej po malejch castech...
nejdriv rozjet treba prvocisla... pak kombinace...

EDIT : to je zrada :-)

Srovnáme rychlosti už zhotovených ??
zvolil jsem si čísla do 1400000 - 10 náhodných hodnot
578 milisekund - mojí verzí :-)

To o-lox : ináč to meranie rychlosti programu by ma zaujímalo ako robíš.. máš nejaký program,tool alebo niečo? a nie je to nahodou tak ze to zavisi od vykonnosti pocitaca?

Rychlost výpočtů na rychlosti počítače pochopitelně závisí, časomíra se dá udělat tak, aby nezávisela - buď standardními funkcemi Getdate a Gettime (přesnost na setinu vteřiny) nebo vlastními prostředky přes přerušení časovače (např. http://mircosoft.ic.cz/download/CAS.PAS).

Používal jsem WinAPI - milisekundy, ne setiny. GetTickCount. A není nemožné ani pohrát si trochu s objektivností měření alespoň podle frekvence CPU - viz QueryPerformanceCounter. Pod DOSem pak assemblerem a čítačem časových značek, to ale nezohledňuje samozřejmě pipeline - architekturu.

K tej Goldbachovej hypoteze ako takej.. myslim ze to uz len takym miernym zamyslenim sa vidiet ze vlastne samotna neplatnost tejto hypotezy je velmi vysoko nepravdepodobna, ked si vezmeme do uvahy ze prvocisla su vylucne neparne ( cesky liche ?? neviem :D ) a v intervale lubovolnych desat cisel ich byva 3-4 myslim a liche + liche = sude takze kombinacia by sa mala najst aj viac krat pri tych vyssich parnych ( sudych )

Ale aj ked je jej neplatnost velmi vysoka, to je asi dovod preco je to len hypoteza, platnost asi nikto nedokazal

To evandar : To s 3-4 v 10 cislech neni pravda, prvocisla jsou stale vzacnejsi a vzacnejsi, milionte je okolo 150M a podle wiki je jich v 10E23 asi 1.9E21 tj v obou pripadech radove 1 v 100 cislech.

To Krychlik : Fiha tak o prvocislach okolo 1000000+ som neuvazoval, ja skor do tej stovky max tsicky.. ale myslim ze pri tych vyskach okolo miliona tam je tolko moznych kombinacii ze aj 1 zo 100 staci ..

Panove muzu vas vyrusit z akademicke diskuze? Prave tenhle priklad taky resim. Vsechno by fungovalo, ale mam problemy s casem. Jestli sem vsechno pochopil, jdou ty kroky po sobe takhle:
1. Eratosthenovo sito pro hodnoty 1 az 1000 000
2. Vytvoril sem si dalsi pole a do nej nacpal 78498 prvocisel (tolik jich je v milionu)
3. vsech nechal psat na sklo pomoci cyklu
while not seekeof do
begin
read(x);
if Sito[X] then writeln('Ouch!') else {tohle je z eratosthenova sita.. proste rve na prvocisla ouch :)}
begin
for i:=1 to 78498 do
begin
for j:=78498 downto i do
begin
Y:=prvo[i]+prvo[j];
if Y=X then begin writeln(X,'=',prvo[i],'+',prvo[j]); break end;
end;
if X=Y then break;
end;
end;
end;
Cyklus se seekeof je tam kvuli tomu, ze to vyhodnocuje aplikace a ja mam za to ze k ukonceni vraci prave eof. Nepomoh by mi to nekdo zrychlit? Aspon nejakej navrh.. diky

Já to udělal takto:
struct {int v,p;}vysl[10];

a=10; // mame jich 10 na vstupu v poli
for (i=0;i<prvocisel;i++)
for (j=prvocisel;j>i;j--)
{suma=(prvo[i]+prvo[j]);
for (b=0;b<a;b++){
if (suma==vstup)
{
vysl[vyslp].p=j;
vysl[vyslp++].v=vstup;
for (k=b;k<a-1;k++)
vstup[k]=vstup[k+1];
a--;
}
if (!a)
goto ven;
}
}

ven: