ProjectEuler v C# - rychlost Vyřešeno

[Rutherther]

Ahoj, před pár dny jsem začal v ProjectElueru, většinou přijdu na to, jak úkol vyřešil, ale mám problém.. a to v rychlosti, můj počítač je pomalý a proto asi i tyto příklady počítá pomalu..

Příklad zápisu:

Kód: Vybrat vše

     BigInteger l = 600851475143;
            BigInteger primefactor = 0;
            BigInteger i = 1;
            while (i < l) {
                if (l % i == 0) primefactor = i;
                i++;
            }
            Console.WriteLine(primefactor);
                Console.ReadKey();

Tohle jsem dělal pro Largest prime factor. Čekal jsem asi 3 minuty a nic, prostě se to za 3 minuty nedokončilo, jak by šlo udělat, aby to bylo rychlejší, pokud je to vada c#, tak jaký jiný jazyk použít? Děkuji za rady

Edit: prime factor je asi něco jiného, ale to je jedno, pak to opravím, hlavně mě teď zajímá, jak to tedy zrychlit?

[Reklama]

[faraon]

No, tak jenom napočítat do tohohle čísla po jedné trvá mému počítači skoro hodinu a půl, přičemž jeho faktorizaci na prvočísla zvládne za zlomek sekundy. Takže tudy cesta určitě nevede!

Kód: Vybrat vše

faraon@tuxbox:~# time factor 600851475143
600851475143: 71 839 1471 6857

real    0m0.095s
user    0m0.003s
sys     0m0.041s


Z toho tvého kódu jsem vyluštil že hledáš největší číslo kterým je to tvoje N beze zbytku dělitelné (fakt to nemá být prvočíslo?). Já bych to zkusil spíš naopak, najít to nejmenší, a tím potom N vydělit pro získání výsledku.
Také nemusíš mít cyklus až do N, stačí do jeho druhé odmocniny, protože větší určitě nebude potřeba.
A s ohledem na to závěrečné dělení bych primefactor na začátku inicializoval na 1, aby ti ta nula nepřichystala drobné překvapení v případě zadání prvočísla.

[Rutherther]

já vlastně ani nevím, jestli to mají být prvočísla, ale spíše ne, protože v zadání bylo, že nějaké číslo má ty prime factory 5, 7, 23, chybělo by tam např. 11, 17 a navíc ja tak velké je jich malo.. Podívej se sám:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Samozřejmě nechci, abyste mi radili, taky mě napadlo, že to budou čísla, kterými to jde dělit, ale jen, když budou první (nevím, jak to popsat, takže příklad: kdyby to šlo dělit číslem 29*5, ale 29 už by tam byla, tak by to už nebyl prime factor)


Nebo ještě prvočísla, kterými to lze dělit.

Díky za radu, já na to nějak přijdu

Btw. Jak jsi zjistil, že to trvalo hodinu a půl? To jsi to nechal běžet?

[faraon]

Kód: Vybrat vše

faraon@tuxbox:~# factor 13195
13195: 5 7 13 29

Takže to má být opravdu největší prvočíslo!

No, potom tě tedy čeká faktorizace zadaného čísla na jednotlivá prvočísla, a nebo můžeš to co jsem napsal minule použít v cyklu (či rekurzi). Když najdeš nejmenší dělitel N, tak jím N vydělíš a začneš znovu hledat další nejmenší, dokud nebude N prvočíslo.

Tu dobu jsem odhadl, zkusil jsem to se setinou toho čísla a dobu vynásobil. Pro přibližný odhad a posouzení že nemá cenu to zkoušet to stačilo

[satik]

Kód: Vybrat vše

static void Main(string[] args)
        {
            Int64 n = 600851475143;
            var primes = Euler(n);
            Console.WriteLine("{0} has primes: {1}, highest is {2}.", n, String.Join(", ", primes.ToArray()), primes.Max());
            Console.ReadKey();
        }

        static List<Int64> Euler(Int64 n)
        {
            var sqrtN = (Int64)Math.Sqrt(n);

            var primes = new List<Int64>();

            bool added = true;
            int i=2;
            while (i < sqrtN && i<n)
            {
                if (n % i == 0)
                {
                    primes.Add(i);
                    added = true;
                    n = n / i;
                }
                else
                {
                    added = false;
                    i++;
                }
            }

            if (!added)
                primes.Add(i);

            return primes;
        }


Zkusil jsem si to napsat, je to i celkem rychlé (stačí tomu na to číslo 600851475143 jen 7000 průchodů cyklem) a najde ti to všechny prvočísla (i to největší, jak je v zadání).

Psal jsem to jen asi 15 minut a moc netestoval, tak tam teoreticky může být nějaká chybka.

[Rutherther]

Satiku, už to nepotřebuji, ale stejně díky.

Rovnou toho využiji a zeptám se.. Jaký je rozdíl mezi int, int64, int32 a int16?

[satik]

číslo za int určuje rozsah
pokud necháš jen int, tak ten má rozsah podle architektury - v 32bit programu 32 bitů, v 64bit programu 64 bitů

[X]

... , většinou přijdu na to, jak úkol vyřešil, ...

Kdo úkol vyřešil? Hned v první větě nepřesnost, chyba, nesmysl? Ty chceš být programátor? To si nedovedu představit ...

[Rutherther]

Promiň za tu chybku, každý se překlikne.. Ale ty to asi bereš tak, že jsem sem vůbec napsal.. Prostě mě zajímalo, jak s tou rychlostí, jestli jde nějak udělat, aby to bylo rychlejší.. A je zde spoustu jiných příspěvků, které se ptají na docela začátečnické věci, tak proč sis vybral zrovna tento?