Stránka 1 z 1
ProjectEuler v C# - rychlost
Napsal: 10 dub 2015 20:16
od 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?
Re: ProjectEuler v C# - rychlost
Napsal: 11 dub 2015 07:32
od 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.
Re: ProjectEuler v C# - rychlost
Napsal: 11 dub 2015 09:01
od 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?
Re: ProjectEuler v C# - rychlost
Napsal: 11 dub 2015 09:20
od faraon
Kód: Vybrat vše
faraon@tuxbox:~# factor 13195
13195: 5 7 13 29Takž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
Re: ProjectEuler v C# - rychlost
Napsal: 11 dub 2015 11:20
od 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.
Re: ProjectEuler v C# - rychlost
Napsal: 11 dub 2015 16:28
od 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?
Re: ProjectEuler v C# - rychlost
Napsal: 11 dub 2015 17:05
od 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ů
Re: ProjectEuler v C# - rychlost
Napsal: 11 dub 2015 17:13
od X
Rutherther píše:... , 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 ...
Re: ProjectEuler v C# - rychlost Vyřešeno
Napsal: 11 dub 2015 19:17
od 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?