Priemgetallen

[SirMemeAlot]

Mede-tweakerts,

Ik ben sinds kort begonnen met de opleiding informatica, en ik moet een opdracht voor maken in C# om alle priemgetallen tussen de 2 en de 100 te laten zien. Het lukt mij niet om alleen de priemgetallen te laten zien, misschien heeft iemand nog een goed idee wat ik zou kunnen toevoegen om als nog alleen de priemgetallen te tonen

C#: 5

 
            var priemgetallen = from p in Enumerable.Range(2, 100)
                                    where p % 2 == 1 
                                    select p;
                foreach (int priemgetal in priemgetallen)
                    Console.WriteLine(priemgetal);
                Console.ReadLine();

Ik hoef niet letterlijk het antwoord, maar een tip in de goede richting word gewaardeerd.

edit; Het is zeker niet de bedoeling dat iemand mij letterlijk de oplossing de oplossing gaat geven. Ik wil liever weten of ik wat betreft code in de goede richting aan het denken ben, en/of ik door middel van een andere algoritme misschien beter de berekening kan laten uitvoeren.

Oftewel ik ben meer op zoek naar tips + advies.

@ Roblll ik moet zeggen had nog niet op deze manier op google gekeken, maar ik kreeg nu direct het antwoord. Iets wat ik liever zelf uit zoek met evt tips of adviezen.

[ Voor 30% gewijzigd door SirMemeAlot op 04-12-2011 15:40 ]

[Nick_S]

Kun je zeggen wat er niet lukt? Als ik google op primes algorithm heb je daar genoeg aanknopingspunten om verder te komen.

[RobIII]

Als je code post, gebruik dan code tags a.u.b.
Verder zie ik geen enkele serieuze poging om te bepalen wat nou een priemgetal is en wat niet. Wat heb je zelf al geprobeerd behalve, toch wel basic, een loop van 2 tot 100? Zie ook onze Quickstart; dat is toch wel het minimale waar je topic aan moet voldoen.

En waarom vind ik met [google=c# calculate prime numbers] een shitload aan info? Wat had je daar zelf al van gevonden, wat voldeed daar niet aan, wat begreep je niet etc. etc.?

Huiswerktopics zijn niet per definitie fout! (getuige de TR die aan dit topic hangt), maar dit neigt toch écht naar een "Kan iemand even... uitleggen hoe ik een priemgetal bereken".

Ik laat dit topic dan ook nog, voorlopig, open om je een kans te geven 't aan te vullen met bovenstaande informatie.

offtopic:
Ik zou zelf voor een for-loop zijn gegaan i.p.v. de 'fancy' LINQ variant. LINQ is in dit geval imho veel te wollig; een simpele for zou al voldoen hier.

for (int i = 2; i <= 100; i += 2) {
    //Do stuff here...
}

[ Voor 65% gewijzigd door RobIII op 04-12-2011 15:32 ]

[Avalaxy]

Wat je kunt doen is ten eerste een for-loop maken die van 2 tot 100 honderd loopt, het enige dat je dan nog hoeft te doen is elke keer dat er geloopt wordt checks uitvoeren op het huidige getal om te kijken of dat getal een priemgetal is.

Er zijn natuurlijk veel efficiëntere algoritmes dan deze 'bruteforce' aanpak, maar dat lijkt me niet passen bij een eerstejaarsopdracht, dat krijg je als het goed is nog

Wat betreft je vraag: gewoon kijken of je getal aan alle voorwaarden voldoet (je hoort het al: if-statements), zo ja: Console.WriteLine(i)

[ Voor 14% gewijzigd door Avalaxy op 04-12-2011 15:24 ]

[Nactive]

Als ik jouw algoritme zie, al heb ik niet helemaal door hoe het juist werkt zal jij gewoon alle even getallen printen.

Een mogelijk algoritme is ook voor elk getal zijn veelvouden aangeven dat ze niet priem zijn.

In pseudo code is dat iets zoals (ben wel niet 100% zeker dat deze code werkt, nog nooit de fucntie geschreven maar iets in die rechting moet wel werken denk ik).

C#:

bool nietPriem[100];
for (int i = 2; i < 100; i++) {
     if (!nietPriem[i]) {
        print i is priem;
        for (int j = i * i; j < 100; j *= i) {
            nietPriem[j] = true;
        }
     }
}

Maar zoals hierboven al is gezegd, met een google op internet zal je direct zeer efficient algoritmes vinden.

[ Voor 8% gewijzigd door Nactive op 04-12-2011 15:57 ]

[Emmeau]

Zoek eens op 'Zeef van Eratosthenes', leuk te implementeren in C# met lists of collections

[ Voor 1% gewijzigd door Emmeau op 04-12-2011 16:00 . Reden: s vergeten in eens ]

[RobIII]

Nactive schreef op zondag 04 december 2011 @ 15:56:

C#:

     if (!nietPriem[i]) {

Famous quote:

Do not put statements in the negative form.

Daarbij; ik zie even niet hoe dit een priemgetal zou moeten bepalen?

[eamelink]

RobIII schreef op zondag 04 december 2011 @ 16:03:
Daarbij; ik zie even niet hoe dit een priemgetal zou moeten bepalen?

Dit is een implementatie van eerder genoemde Sieve of Eratosthenes . De inner loop klopt alleen niet helemaal. Het idee is dat je nergens expliciet priemgetallen zoekt, maar niet-priemgetallen systematisch wegfiltert.

[ Voor 22% gewijzigd door eamelink op 04-12-2011 16:09 ]

[Nactive]

In binnenste lus moeten het + in plaats van * zijn

C#:

for (int j = i + i; j < 100; j += i)

Idee is gewoon indien een getal priem is zijn al zijn veelvouden niet meer priem ...

[RobIII]

eamelink schreef op zondag 04 december 2011 @ 16:06:
[...]

Dit is een implementatie van eerder genoemde Sieve of Eratosthenes . De inner loop klopt alleen niet helemaal.

Dan hebben we opeens een heleboel nieuwe priemgetallen
Ik probeerde te hinten naar 't feit dat 't niet doet wat 't zou moeten doen

Nactive schreef op zondag 04 december 2011 @ 16:09:
In binnenste lus moeten het + in plaats van * zijn

Of 2 * i en j += i inderdaad.
Wat ik dan wel weer een beetje jammer vind is dat 't TS op een zilveren schaaltje wordt gepresenteerd...

Give a man a fish and feed him for a day. Teach a man how to fish and feed him for a lifetime.

Toch wel een beetje 't Devschuur credo.

[ Voor 36% gewijzigd door RobIII op 04-12-2011 16:13 ]

[SeatRider]

Zou je niet wegkomen met

C#:

 
Console.WriteLine('2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97');

?

[ Voor 13% gewijzigd door SeatRider op 04-12-2011 16:14 ]

[RobIII]

SeatRider schreef op zondag 04 december 2011 @ 16:14:
Zou je niet wegkomen met

C#:

 
Console.WriteLine('2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97');

?

De standaard "grap" bij programmeerles. En nee, daar kom je niet mee weg doorgaans.

[Jegorex]

Ik heb geen idee hoe LINQ(?) werkt, maar het lijkt erop dat je in de startpost alle oneven getallen weergeeft.
"p % 2 == 1" zal true geven als p oneven is.

Een oplossing zou zijn om p te delen door 2, 3, 4 enz. en te kijken of er een heel getal uitkomt.
Dit kun je ook nog weer optimaliseren, maar dat kun je zelf wel verder uitzoeken.

[SirMemeAlot]

In m'n startpost kom ik inderdaad uit op alle oneven getallen. Ik moet de berekening daarvan aanpassen, maar heb er nog geen goede oplossing voor kunnen bedenken.

Ik mag helaas niet met for loops werken, omdat we het in LINQ moeten doen.

[ Voor 14% gewijzigd door SirMemeAlot op 04-12-2011 16:32 ]

[Jaap-Jan]

RobIII schreef op zondag 04 december 2011 @ 16:09:
(...)
Toch wel een beetje 't Devschuur credo.

Hier een stem voor Terry Pratchett's versie, die ik al eerder genoemd had.

[RobIII]

SirMemeAlot schreef op zondag 04 december 2011 @ 16:29:
In m'n startpost kom ik inderdaad uit op alle oneven getallen. Ik moet de berekening daarvan aanpassen, maar ik dat moet oplossen is nog niet helemaal duidelijk.

Begin eens met 't schrijven van, ik roep maar wat, een "isPrime()" functie die 1 parameter (het getal waarvan je wil bepalen of 't een priemgetal is of niet) verwacht en een bool returned als result:

C#:

bool isPrime(int number) {
//Implementation here
}

Vervolgens doe je de loop (be it in Linq of in een for-loop of whatever):

code:

iterate 2 to 100 {
  if isPrime(iterator)
    print iterator
}

SirMemeAlot schreef op zondag 04 december 2011 @ 16:29:
Ik mag helaas niet met for loops werken, omdat we het in LINQ moeten doen.

Wat is dat nou voor gaar requirement? Leraar die de popi-jopie wil uithangen Of gaat dit hoofdstuk specifiek over LINQ ofzo? Ik zie dat requirement overigens ook niet in de topicstart staan. Dat was wel handig geweest even te vermelden dan.

[ Voor 18% gewijzigd door RobIII op 04-12-2011 16:37 ]

[kestemodon]

Hoe wij het deden bij matlab was een for-lus maken tot 100.
Dan getal per getal vragen of een van de vorige getallen een natuurlijke getal geeft...
Indien niet dan heb je een priemgetal.

[Anoniem: 376120]

Als je met LINQ moet werken kan je heel makkelijk de 'zeef van Eratosthenes' toepassen , of toch bijna.

C#: priem

IEnumerable<int> priem = Enumerable.Range(2, 98);
for (int i = 0; i < priem.Count(); i++)
            {
                int current = priem.ElementAt(i);
                priem = from p in priem
                        where p % current != 0 || p == current
                        select p;
            }

Omslachtig maar zou moeten werken.

[pientertje]

Ik zou beginnen met kijken of je van één getal kan zeggen of dit wel of geen priemgetal is. Dit voor de getallen van 0 tot 100 doen is kinderspel.

Om te kijken of iets een priemgetal is gebruik je de definitie van een priemgetal:

Een priemgetal is een natuurlijk getal groter dan 1 dat slechts deelbaar is door 1 en door zichzelf.

Als je wil kijken of een getal een priemgetal is moet je testen op deelbaarheid door alle getallen van 2 tot GETAL-1. Deelbaarheid testen doe je met een modulo, iets is deelbaar door iets anders als de rest nul is.

Het resultaat is dus (pseudo)

code:

for n in range(0,100):
    is_priem = True
    for x in range(2,n):
        if n%x == 0:
            is_priem = False
            break
    if is_priem:        
        print n,"is priem"

[Jegorex]

pientertje schreef op zondag 04 december 2011 @ 16:39:
[...]

Als je wil kijken of een getal een priemgetal is moet je testen op deelbaarheid door alle getallen van 2 tot GETAL-1 t/m wortel(GETAL). Deelbaarheid testen doe je met een modulo, iets is deelbaar door iets anders als de rest nul is.

[pientertje]

Weet ik, maar dat zijn slechts optimalisaties. Ik wilde het niet complexer maken dan nodig was.

[pedorus]

Anoniem: 376120 schreef op zondag 04 december 2011 @ 16:34:
Als je met LINQ moet werken kan je heel makkelijk de 'zeef van Eratosthenes' toepassen , of toch bijna.

C#: priem

IEnumerable<int> priem = Enumerable.Range(2, 98);
for (int i = 0; i < priem.Count(); i++)
            {
                int current = priem.ElementAt(i);
                priem = from p in priem
                        where p % current != 0 || p == current
                        select p;
            }

Omslachtig maar zou moeten werken.

If you're using a loop, you're doing it wrong (weet niet meer hoe ik eraan kom, hier bijvoorbeeld). Zoiets dus:

quote: http://www.codethinked.co...the-sieve-of-eratosthenes

C#:

var primes = Enumerable.Range(2, (int)maxSquareRoot + 2)
    .Aggregate(Enumerable.Range(2, max - 1).ToArray(), (sieve, i) =>
    {
        if (sieve[i - 2] == 0) return sieve;
        for (int m = 2; m <= max / i; m++)
            sieve[i * m - 2] = 0;
        return sieve;
    })
    .Where(n => n != 0);

Edit: Foutfoutfout, daar zie ik ook een loop, ik bedoel dus:

C#:

            var primes = Enumerable.Range(0, (int)Math.Sqrt(max)).Aggregate(
                Enumerable.Range(2, max - 1).ToList(),
                (sieve, i) =>
                {
                    sieve.RemoveAll(n => n > sieve[i] && n % sieve[i] == 0);
                    return sieve;
                });

Maar dat is vast niet iets dat TS begrijpt, TS zoekt meer zoiets als wat je vind als je de twee relevante engelse trefwoorden zoekt op Google en op "ik doe een gok" drukt. Dat betekend dus bedenken wat er in plaats van "where p % 2 == 1 " wel had moeten staan. Misschien iets met nog een lijstje getallen van 2-(int)wortel(nummer) ofzo.

[ Voor 11% gewijzigd door pedorus op 04-12-2011 19:22 ]

[RayNbow]

SirMemeAlot schreef op zondag 04 december 2011 @ 16:29:
Ik mag helaas niet met for loops werken, omdat we het in LINQ moeten doen.

Hier is een hint voor een LINQ oplossing:

C#:

var primes = from p in Enumerable.Range(2, 100)
             where isPrime(p)
             select p;


bool isPrime(int n)
{
    return factors(n).Take(2).Last(n) == n;
}


IEnumerable<int> factors(int n)
{
    // yield alle delers van n (inclusief 1 en n)
}

Let op: Bij deze aanpak heb ik geen rekening gehouden met efficientie!

[martin149]

Wat je weer van de delers van priemgetallen is dat deze delers:
-Oneven zijn (oneven is enkel te delen door 2 oneven getallen, 2 is echter een uitzondering)
-De delers kleiner zijn of gelijk aan de wortel van het priemgetal

Van het priemgetal weet je dat:
-De priemgetallen een som van andere priemgetallen, mooi als controle.
-De priemgetallen eindigen op een 1,3,7 of 9 (m.u.v. 5 en 2)

[Soultaker]

Nactive schreef op zondag 04 december 2011 @ 16:09:
In binnenste lus moeten het + in plaats van * zijn

C#:

for (int j = i + i; j < 100; j += i)

Nee, * is goed hier, en het is juist de meest efficiënte manier om het probleem aan te pakken. Beginnen bij i² volstaat omdat alle lagere getallen ofwel priem zijn, ofwel een kleinere priemfactor dan i hebben, en dus al eerder weggestreept waren.

Jouw versie is juist een veelgemaakte "fout" in de implementatie die het algoritme veel trager maakt (hoewel het nog wel het correcte antwoord oplevert).

SeatRider schreef op zondag 04 december 2011 @ 16:14:
Zou je niet wegkomen met

C#:

 
Console.WriteLine('2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97');

?

Of, net iets minder flauw:

C#:

from p in Enumerable.Range(2, 100)
where p == 2 || p == 3 || p == 5 || p == 7 || p%2 && p%3 && p%5 && p%7;

(Ik kan trouwens geen LINQ -- ik extrapoleer maar wat op basis van de code in de TS.)

RobIII schreef op zondag 04 december 2011 @ 16:15:
De standaard "grap" bij programmeerles. En nee, daar kom je niet mee weg doorgaans.

Tja, is dat de schuld van de programmeur of van de docent? Hij zou ook gewoon kunnen vragen om de isPrime(int num) functie te implementeren die jij al noemde (of bijvoorbeeld getPrimes(int max) om alle priemgetallen tot en met max op te leveren).

Uitvoer printen en hardcoded limieten zijn bijzaken. Beetje onzinnig om dat onderdeel van het probleem te maken als het om het algemene algoritme te doen was.

[Icekiller2k6]

edit:
ik moet leren alle posts te lezen

Tja je kunt gewoon de zeef van Eratosthenes gebruiken.. dan zou het niet echt moeilijk mogen zijn .. ;-)

Wikipedia: Zeef van Eratosthenes

betekend feitelijk dat je opzoek gaat of het huidig getal een veelvoud voorkomt.. zoja deze verwijderen..
Simpele manier is een boolean array bijhouden.. en dan op false of true zetten .. etc

[ Voor 64% gewijzigd door Icekiller2k6 op 04-12-2011 21:08 ]

[whoami]

SirMemeAlot schreef op zondag 04 december 2011 @ 16:29:
Ik mag helaas niet met for loops werken, omdat we het in LINQ moeten doen.

W-T-F.
Ik vond het al raar dat je in je OP met LINQ aan de slag was; maar dit is toch echt wel een raar requirement. Leren programmeren gaat 'm over denken in abstracties en algoritmes leren ontwikkelen / ontdekken.
Niet over het al of niet een bepaalde technologie aan te wenden (die dan ook nog eens op een veel 'functionelere' manier werkt).

Maar goed, daar ben je natuurlijk niets mee.

[arnold_m]

Soultaker schreef op zondag 04 december 2011 @ 20:58:
[...]

Nee, * is goed hier, en het is juist de meest efficiënte manier om het probleem aan te pakken. Beginnen bij i² volstaat omdat alle lagere getallen ofwel priem zijn, ofwel een kleinere priemfactor dan i hebben, en dus al eerder weggestreept waren.

In je oorspronkelijke code stond :

code:

         for (int j = i * i; j < 100; j *= i) {

De * is inderdaad goed maar de *= moet toch echt += zijn anders streep je alleen de machten van i weg in plaats van alle veelvouden vanaf i*i.

[D-Raven]

pedorus schreef op zondag 04 december 2011 @ 18:56:
[...]

If you're using a loop, you're doing it wrong (weet niet meer hoe ik eraan kom, hier bijvoorbeeld). Zoiets dus:

[...]

Edit: Foutfoutfout, daar zie ik ook een loop, ik bedoel dus:

C#:

            var primes = Enumerable.Range(0, (int)Math.Sqrt(max)).Aggregate(
                Enumerable.Range(2, max - 1).ToList(),
                (sieve, i) =>
                {
                    sieve.RemoveAll(n => n > sieve[i] && n % sieve[i] == 0);
                    return sieve;
                });

Maar dat is vast niet iets dat TS begrijpt, TS zoekt meer zoiets als wat je vind als je de twee relevante engelse trefwoorden zoekt op Google en op "ik doe een gok" drukt. Dat betekend dus bedenken wat er in plaats van "where p % 2 == 1 " wel had moeten staan. Misschien iets met nog een lijstje getallen van 2-(int)wortel(nummer) ofzo.

toon volledige bericht

Echt... wat een belachelijke manier om een priem getal te berekenen....

[Soultaker]

arnold_m schreef op zondag 04 december 2011 @ 22:33:
De * is inderdaad goed maar de *= moet toch echt += zijn anders streep je alleen de machten van i weg in plaats van alle veelvouden vanaf i*i.

Ah, daar heb je gelijk in. Dan zijn we het eens: de eerste + moet gewoon een * zijn, en de tweede een +, zodat alle veelvouden van i tussen i² en n weggestreept worden. ('t Was overigens niet mijn code!)

[.oisyn]

Soultaker schreef op zondag 04 december 2011 @ 20:58:
Of, net iets minder flauw:

C#:

from p in Enumerable.Range(2, 100)
where p == 2 || p == 3 || p == 5 || p == 7 || p%2 && p%3 && p%5 && p%7;

Je moet nog een paar !=0's inserten, C# heeft net als Java geen implicit bool conversion

[bwerg]

Soultaker schreef op zondag 04 december 2011 @ 20:58:
Tja, is dat de schuld van de programmeur of van de docent? Hij zou ook gewoon kunnen vragen om de isPrime(int num) functie te implementeren die jij al noemde (of bijvoorbeeld getPrimes(int max) om alle priemgetallen tot en met max op te leveren).

Van de programmeur, beetje begrijpend lezen mag wel. Kan je wel gelijk hebben maar als je zakt heb je d'r ook niks aan. We weten trouwens niet wat de exacte verwoording van de opdracht is, dus ach...

[4Real]

Wat nou als je een lijst met letters neemt die kwa ASCII code gelijk staan aan de priemgetallen en dan in een loopje de ASCII waarde weergeeft

[RobIII]

4Real schreef op maandag 05 december 2011 @ 10:52:
Wat nou als je een lijst met letters neemt die kwa ASCII code gelijk staan aan de priemgetallen en dan in een loopje de ASCII waarde weergeeft

En zo nog 1001 andere manieren van 't "grapje" Daar kom je op 't voortgezet onderwijs misschien een keer mee weg, bij een (beetje) opleiding informatica niet.

Zullen we 't nou ontopic houden?

[SaphuA]

.

[ Voor 98% gewijzigd door SaphuA op 31-01-2022 15:52 ]

[Soultaker]

.oisyn schreef op maandag 05 december 2011 @ 02:14:
Je moet nog een paar !=0's inserten, C# heeft net als Java geen implicit bool conversion

Ah, bedankt. Ik bedoel natuurlijk: die fouten had ik er ingelaten voor de TS.

bwerg schreef op maandag 05 december 2011 @ 07:41:
Van de programmeur, beetje begrijpend lezen mag wel. Kan je wel gelijk hebben maar als je zakt heb je d'r ook niks aan.

Ja, daar kwam ik snel genoeg achter toen ik en mijn practicumpartner onze routine om willekeurige driehoekjes op een bitmap te tekenen opnieuw moesten schrijven omdat in de opdracht stond dat 'ie alléén gelijkbenige driehoeken met de basis evenwijdig aan de x-as moest kunnen tekenen.

Als ik zo'n vak zou organiseren zou ik gewoon een klasse met de benodigde methoden met documentatie van wat ze moeten doen geven, en de studenten de implementatie in laten vullen. Achteraf run je er een van te voren gemaakte testsuite over en dan zie je zo wie welke randgevallen vergeten heeft, en of de performance een beetje te pruimen is.

[Cornholio]

Klopt het dat dit de opdracht is, Topic opener?

Geef alle priemgetallen tussen 2 en 100 (d.w.z. [2,3,5,7,11, …]).
Hint: Een getal is een priemgetal als de lijst van zijn delers de lengte 2 heeft.

In dat geval weet ik op welke school jij zit ;-)

Ik zou gewoon een for-loop doen van 2 t/m 100. Dan pak je elke uitkomst daarvan, en deelt het met elke getal kleiner dan die (ook weer met een for-loop). Dan doe je de eerste module de tweede, en als dat 0 is, voeg je het getal toe aan een ArrayList.
Hier moet je ook nog wat mee doen, let vooral op de laatste zin van de opdracht: "lijst van delers de lengte 2".

Succes

[dtech]

Wat ik zelf een simpele toch efficient te implementeren manier vind is: een priemgetal is een priemgetal is als het niet door alle voorgaande priemgetallen te delen is. Is denk ik ook een manier die je in LINQ kan implementeren, al ken ik het daar bij lange na niet goed genoeg voor.

Ik weet dat het een beetje op SQL lijkt, en daar zou het zeker in moeten kunnen (ook zonder stored procedure)

Krijg je zoiets:

code:

make a collection priemen

for every i in [2..99]
    if not i deelbaarDoor any priem in priemen
        add i to priemen

of voor de mensen die de notatie kunnen lezen:

code:

Priemen = { i | ∀x( i mod x ≠ 0 ∧ x ≠ i ∧ x ∈ Priemen) }

Ik vind het best belangrijk om te weten of het hier specifiek om implementatiewerk gaat of om echt een eenvoudig algoritme bedenken. In het tweede geval vind ik het bizar dat LINQ wordt vereist maar is bovenstaande pseudocode al het antwoord, dat je eigenlijk zelf moet bedenken. Ik het eerste geval had je makkelijk een priem-algoritme kunnen googlen en het omschrijven naar LINQ.

@Cornholio
Deze vraag is zo standaard dat je hier echt niet een school uit zou moeten kunnen afleiden

[ Voor 7% gewijzigd door dtech op 05-12-2011 21:41 ]

[pedorus]

dtech schreef op maandag 05 december 2011 @ 21:33:
Wat ik zelf een simpele toch efficient te implementeren manier vind is: een priemgetal is een priemgetal is als het niet door alle voorgaande priemgetallen te delen is.

Oftewel de eerder genoemde Zeef van Eratosthenes.

Is denk ik ook een manier die je in LINQ kan implementeren, al ken ik het daar bij lange na niet goed genoeg voor.

Zie hierboven Ik denk enkel dat efficiënte oplossingen en linq niet samen gaan, tenzij je de code-size bedoelt. Efficiency is toch geen issue bij het berekenen van tot max. 100. Sowieso, waarom dan niet op zijn minst de Zeef van Atkin gebruiken.

[Soultaker]

pedorus schreef op maandag 05 december 2011 @ 21:48:
Sowieso, waarom dan niet op zijn minst de Zeef van Atkin gebruiken.

Waar komt de snelheidswinst bij de Zeef van Atkin vandaan? De pseudo-code op Wikipedia eindigt doodleuk met een lusje ("eliminate composites by sieving") waarin precies zo gezeefd wordt als bij Eratosthenes (behalve dat 2 en 3 overgeslagen worden). De paper van Atkin en Bernstein noemt nog als voordeel dat slechts O(N^½) geheugen nodig is, maar dat zie ik in die implementatie ook niet terug. Wat is dan precies het voordeel van die routine?

[Zoijar]

Zeef-algoritmes zijn toch sowieso nutteloos? Snel probabilistisch testen (Miller–Rabin ofzo) en de overblijvers nog even nagaan.

[pedorus]

Aangezien je de overblijvers toch moet nagaan, kun je maar beter een deterministische test gebruiken, AKS of de deterministische variant van Miller ofzo. Dan nog zal Atkin vast sneller zijn als je alle priemgetallen moet vinden.

Het geheugengebruik van Atkin (en ook Eratosthenes) komt van de segmenteerde variant. Het is dus vooral een kwestie van slechts delen van het probleem tegelijkertijd aanpakken. Voordeel van Atkin is bijvoorbeeld dat het deelalgoritmes betreft die bepaalde soorten priemgetallen testen (60k+x met x steeds uit vaste verzameling) en gemiddeld iets efficiënter zijn. Ook is Atkin nog eens makkelijker te parallelliseren. Ik heb niet het hele algoritme bekeken ofzo, maar de link naar de implementatie staat erbij, en ik heb het Wikipedia-artikel overgeslagen en het echte artikel bekeken

[Grijze Vos]

Volgens mij gaat het probleem van de TS niet echt over het kiezen tussen verschillende complexe algoritmes jongens, maar moet hij gewoon iets doen met Linq wat iets moeilijker is dan een triviale select statement.

Waarom niet gewoon wordt gevraagd om dit in Haskell o.i.d. te doen is mij dan weer een raadsel, want dat het in C##+Linq gedaan moet worden voegt alleen maar ruis toe.

[cflink]

Als iedereen de smaak van het zoeken naar priemgetallen te pakken heeft is het derder probleem van Project Euler wel een leuk vervolg:

quote: http://projecteuler.net

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

What is the largest prime factor of the number 600851475143 ?

Dit los je niet zomaar op met een eenvoudig algoritme, hierbij moet je efficient te werk gaan om niet tegen timeouts of memory errors aan te lopen. Succes!

[.oisyn]

Nou zo efficient hoef je niet te programmeren. Ik zou niet eens gaan zeven. Sterker nog, het hele concept van priemgetallen heb je niet nodig bij je oplossing.

.edit: ok, waarom vindt PHP 600851475143 % 3 == 0 . Moet je fmod() gebruiken, waar gaat dat in hemelsnaam over.
Anyway, mijn oplossing is 5 regels code, waarvan een voor het initializeren van een variabele met 600851475143 en de ander voor het uitvoeren van het antwoord. Running time zo goed als instant (heb geen zin om het te meten). Memory usage: 2 variabelen.

.edit2: haha, ik zit eens door de verschillende oplossingen te bladeren op Project Euler voor dat probleem. Het is echt frappant hoeveel mensen een isPrime() functie nodig denken te hebben

[ Voor 72% gewijzigd door .oisyn op 09-12-2011 00:30 ]

[Soultaker]

Ik vermoed dat je code vergelijkbaar is met de mijne:

Python:

n = 600851475143
i = 2
while i*i <= n:
        if n%i: i += 1
        else:   n /= i
print n

(De looptijd is linear in de grootte van het antwoord, dus inderdaad laag aangezien het antwoord vrij klein is.)

Dat vereist toch wel enig getaltheoretisch inzicht. Als je niet (desnoods zonder er bij stil te staan) de hoofdstelling van de rekenkunde toepast, dan kom je al snel uit bij een oplossing waarbij je voor elk priemgetal gaat kijken of het een deler is (of, omgekeerd, bij elke deler of het een priemgetal is).

offtopic:
Wanneer krijgen we nu eens syntax highlighting voor Python?

[ Voor 10% gewijzigd door Soultaker op 09-12-2011 01:56 ]

[.oisyn]

Klopt

PHP:

$v = 600851475143;

for ($i = 2; $i*$i <= $v; $i++)
    while ($i < $v && fmod($v, $i) == 0)
        $v /= $i;

echo $v;

En dan zie je sommigen er nog een && isPrime($i) tussenproppen op regel 4, waarin ze natuurlijk weer in een loopje gaan testen op delers om te kijken of het een priem is . Maar als v deelbaar is door i, dan impliceert dat al dat i priem is, want alle kleinere delers zijn al uit v gehaald.

.edit: de looptijd is trouwens O(k^1/2), niet O(k)

[ Voor 59% gewijzigd door .oisyn op 09-12-2011 10:58 ]

[Soultaker]

Jouw versie klopt trouwens niet helemaal: als het getal meer dan één keer door de grootste priemfactor te delen is, geeft jouw code ten onrechte 1 terug (maakt voor dit specifieke geval niet uit, natuurlijk).

Aangenomen dat je met K het antwoord bedoelt is O(K^½) geen geldige upperbound; tegenvoorbeelden zijn bijvoorbeeld N=p² of N=p(p+2) (indien p en p+2 priemgetallen zijn).

Het geval waarin N zelf priemgetal is, is natuurlijk een belangrijke uitzondering: dan geldt K=N maar je hebt slechts O(K^½) iteraties nodig om dat te bepalen. Vandaar dat O(min(N^½, K)) wél een geldige bovengrens is.

[Zoijar]

Je kan ook nog alle even getallen skippen. Dus volgens mij kan je gewoon $i+=2 doen in je loop als simpele optimalisatie (als je begint bij 3).

[Marcj]

Als je een echt efficiënt algoritme hebt gemaakt, kun je tenminste ook probleem 357 oplossen. Hiervoor ben je toch echt alle priemgetallen nodig tot 100.000.000. Deze oplossing is trouwens wel binnen 2 seconden uit te rekenen (met behulp van een Zeef van Eratosthenes, met optimalisaties als alleen de oneven getallen afhandelen en dan voor elke p dan p+2*n*p uitfilteren).

[pedorus]

Hmm, probleem 357 is gemakkelijk te brute-forcen, waarbij je eigenlijk niet eens alle priemgetallen in het geheugen nodig hebt, alleen genoeg tijd. Je ziet ook dat relatief veel mensen die hebben opgelost. (Ja, ik neem de 1 min. limiet niet in beschouwing.) Probleem 355 is ook iets met priemgetallen, daar heb je wel een echt algoritme voor nodig.

[Marcj]

pedorus schreef op vrijdag 09 december 2011 @ 09:47:
Hmm, probleem 357 is gemakkelijk te brute-forcen, waarbij je eigenlijk niet eens alle priemgetallen in het geheugen nodig hebt, alleen genoeg tijd. Je ziet ook dat relatief veel mensen die hebben opgelost. (Ja, ik neem de 1 min. limiet niet in beschouwing.) Probleem 355 is ook iets met priemgetallen, daar heb je wel een echt algoritme voor nodig.

Kun je ook brute-forcen binnen een redelijke tijd? Volgens mij ben je echt uren bezig. Mijn implementatie doet het nu in 1.22 seconden.

[.oisyn]

Soultaker schreef op vrijdag 09 december 2011 @ 04:03:
Jouw versie klopt trouwens niet helemaal: als het getal meer dan één keer door de grootste priemfactor te delen is, geeft jouw code ten onrechte 1 terug (maakt voor dit specifieke geval niet uit, natuurlijk).

Klopt idd, aangepast

Vandaar dat O(min(N^½, K)) wél een geldige bovengrens is.

Nee, dat is ook geen geldige bovengrens. Bij 2^p is k altijd 2, maar dan is ie O(p)

Zoijar schreef op vrijdag 09 december 2011 @ 09:01:
Je kan ook nog alle even getallen skippen. Dus volgens mij kan je gewoon $i+=2 doen in je loop als simpele optimalisatie (als je begint bij 3).

Je kunt ook om en om +=2 en +=4 doen, dan skip je ook de getallen deelbaar door 3 (wel beginnen bij 5 natuurlijk). Of je doet steeds de sequence += { 4, 2, 4, 2, 4, 6, 2, 6 }, dan skip je ook deelbaar door 5 (beginnen bij 7). Etc.

[ Voor 32% gewijzigd door .oisyn op 09-12-2011 11:33 ]

[Soultaker]

.oisyn schreef op vrijdag 09 december 2011 @ 10:59:
Nee, dat is ook geen geldige bovengrens. Bij 2^p is k altijd 2, maar dan is ie O(p)

Oh ja, balen. Laten we het dan gemakshalve op O(N^½) houden want dat geldt zeker (al zal het algoritme voor getallen met veel priemfactoren aanzienlijk sneller zijn).

[Zoijar]

.oisyn schreef op vrijdag 09 december 2011 @ 10:59:
Je kunt ook om en om +=2 en +=4 doen, dan skip je ook de getallen deelbaar door 3 (wel beginnen bij 5 natuurlijk). Of je doet steeds de sequence += { 4, 2, 4, 2, 4, 6, 2, 6 }, dan skip je ook deelbaar door 5 (beginnen bij 7). Etc.

Ja, ik snap dat je het uit kan breiden, maar met een hele simpele wijziging de helft niet checken scheelt natuurlijk wel. Je kan ook een harde ondergrens voor de primegap bepalen.