zoeken naar priemgetallen m.b.v. for loop

[umask]

hoi, ik snap niet precies wat er gebeurt en waarom bepaalde handelingen zijn gekozen om te weten te komen of het een priemgetal is of niet.. zou iemand aub kunnen uitleggen wat de precieze gedachte hierachter is en waarom de code alsnog..
Waarom gebruikt deze persoon bijv. (i/j) in de 2e for loop? en bij modulo staat dat als er geen rest is, dat uit de 2e for loop moet gaan, gaat deze helemaal uit de for loop of alleen de 2e? daarnaast als i = 2 en j = 2 wordt modulo 0, dan gaat die uit de for loop en neem ik aan dat die weer verder gaat met de volgende regels code? maar waarom checkt hij specifiek of j groter is dan het getal dat uit i / j uitkomt?

C#:

int i, j;
         
for (i = 2; i < 100; i++) 
{
   for (j = 2; j <= (i / j); j++) 
   {
      if ((i % j) == 0) break; // if factor found, not prime
   }
   if (j > (i / j)) Console.WriteLine("{0} is prime", i);
}

[Wiebeltje]

i / j => 6 / 3. Het heeft geen zin meer om 6 te delen door 4 of 5. Zodra je over de helft van i zijn waarde gaat houd het op. Omdat er <= (i/j) staat wordt bij i = 6, j 4. Vandaar ook de if na de for loop. Als j namelijk groter is dan de helft van i is die alleen deelbaar door zichzelf en 1.

De break stopt alleen de twee for loop. Niet de buitenste.

Alle complexiteit is toegevoegd om de code efficiënter te maken.

[ Voor 8% gewijzigd door Wiebeltje op 15-11-2019 21:52 ]

[umask]

Wiebeltje schreef op vrijdag 15 november 2019 @ 21:47:
Zodra je over de helft van i zijn waarde gaat houd het op. Omdat er <= (i/j) staat wordt bij i = 6, j 4.

Ik heb een output gegenereerd, j wordt niet zo vaak opgeteld?? en bij die 2e iteratie voldoet het niet aan de if-statement, maar gaat het nog steeds naar de laatste if-statement? + j wordt ook niet opgeteld?

code:

Iteration: 1 [i = 2, j = 2] and [cond.: 2 / 2 = 1] and [mod: 2 % 2 = 0]
2 is prime

Iteration: 2 [i = 3, j = 2] and [cond.: 3 / 2 = 1] and [mod: 3 % 2 = 1]
3 is prime

Iteration: 3 [i = 4, j = 2] and [cond.: 4 / 2 = 2] and [mod: 4 % 2 = 0]
4 is not a prime

Iteration: 4 [i = 5, j = 3] and [cond.: 5 / 3 = 1] and [mod: 5 % 3 = 2]
5 is prime

Iteration: 5 [i = 6, j = 2] and [cond.: 6 / 2 = 3] and [mod: 6 % 2 = 0]
6 is not a prime

Iteration: 6 [i = 7, j = 3] and [cond.: 7 / 3 = 2] and [mod: 7 % 3 = 1]
7 is prime

Iteration: 7 [i = 8, j = 2] and [cond.: 8 / 2 = 4] and [mod: 8 % 2 = 0]
8 is not a prime

Iteration: 8 [i = 9, j = 3] and [cond.: 9 / 3 = 3] and [mod: 9 % 3 = 0]
9 is not a prime

Iteration: 9 [i = 10, j = 2] and [cond.: 10 / 2 = 5] and [mod: 10 % 2 = 0]
10 is not a prime

Iteration: 10 [i = 11, j = 4] and [cond.: 11 / 4 = 2] and [mod: 11 % 4 = 3]
11 is prime

[ Voor 49% gewijzigd door umask op 16-11-2019 01:10 ]

[Wiebeltje]

code:

# Bij i = 3 komt hij dus niet eens in de for loop. 
# 3 / 2 = 1 omdat alles naar beneden wordt afgerond.
for (j = 2; 2 <= (3 / 2); j++) 

Daarna:
if (2 > (3 / 2)) {
    Console.WriteLine("{0} is prime", i);
}

Sorry ik zit op mobiel dus ik kan het niet goed uitwerken. Hoop dat het iets duidelijker is. Ik moest ook goed lezen wat er staat en ik doe dit voor mijn werk dus heel makkelijk te begrijpen is het niet

j wordt niet zo snel opgeteld omdat die break er voor zorgt dat de loop stopt zodat hij een breuk vind. Dus bij 8 / 2 houd het al op

[ Voor 13% gewijzigd door Wiebeltje op 15-11-2019 22:37 ]

[umask]

# Bij i = 3 komt hij dus niet eens in de for loop.

maar je deelt het toch gewoon door j?? Oh wacht dan probeer je 2 < 1 te vergelijken.. oké dit snap ik

j wordt niet zo snel opgeteld omdat die break er voor zorgt dat de loop stopt zodat hij een breuk vind. Dus bij 8 / 2 houd het al op

bedoel je dat de iteratie ophoud?? en kun je wat specifieker zijn, want ik zie gewoon dat j nog steeds na 8 / 2 wordt opgeteld?

Hoe kan het trouwens dat j van 3 naar 2 is gegaan bij iteratie 5??

code:

Iteration: 5 [i = 6, j = 2] and [cond.: 6 / 2 = 3] and [mod: 6 % 2 = 0]
6 is not a prime

[ Voor 40% gewijzigd door umask op 15-11-2019 23:03 ]

[Wiebeltje]

code:

i = 3
j = 2
for (j = 2; j <= (i / j); j++)
for (j = 2; 2 <= (3 / 2); j++)
for (j = 2; 2 <= 1; j++)

Basically staat er :
if (2 <= 1)
Dat is niet zo dus j wordt niet met 1 opgehoogd de code in de binnenste for loop wordt niet uitgevoerd

Verder:

code:

   for (j = 2; j <= (8 / j); j++) 
   {
      if ((8 % 2) == 0) {
          break; // if factor found, not prime
          // Hij komt hier bij de break want 0 == 0. 
          // Code gaat verder bij onderstaande if
      }
   }
   if (2 > (8 / 2)) { // 2 is niet groter dan 4
      Console.WriteLine("{0} is prime", i);
   }

Je kan het beste na elke if of for statement alle variabelen uitprinten zodat je ziet wat er precies gebeurd. Naar mate de primes groter worden is het misschien ook makkelijker te begrijpen

[umask]

Wiebeltje schreef op vrijdag 15 november 2019 @ 23:08:
Je kan het beste na elke if of for statement alle variabelen uitprinten zodat je ziet wat er precies gebeurd. Naar mate de primes groter worden is het misschien ook makkelijker te begrijpen

dankjewel voor het advies, maar hoe komt het dat j weer terug van 3 naar 2 gaat?

[Wiebeltje]

Ik snap je vraag niet helemaal. j wordt nergens minder behalve dat hij "gereset" wordt zodra er een nieuwe iteratie van i is omdat je dan weer "vers" bij de binnenste for statement komt.

[Jackxl]

Door de assignment j=2. die wordt telkens als de tweede for loop begint opnieuw toegekend uitgevoerd.

[ Voor 9% gewijzigd door Jackxl op 15-11-2019 23:20 ]

[umask]

Jackxl schreef op vrijdag 15 november 2019 @ 23:19:
Door de assignment j=2. die wordt telkens als de tweede for loop begint opnieuw toegekend uitgevoerd.

Kijk de onderstaande verward me, want hoe kan het dat j bij iteratie 4 dan alsnog 3 wordt, want bij iteratie 3 is het uit de for loop geweest, dus zou die eigenlijk toch bij 2 weer moeten beginnen?

code:

Iteration: 3 [i = 4, j = 2] and [cond.: 4 / 2 = 2] and [mod: 4 % 2 = 0]
4 is not a prime

Iteration: 4 [i = 5, j = 3] and [cond.: 5 / 3 = 1] and [mod: 5 % 3 = 2]
5 is prime

Iteration: 5 [i = 6, j = 2] and [cond.: 6 / 2 = 3] and [mod: 6 % 2 = 0]
6 is not a prime

Wacht ik printte deze te vroeg, ik heb een andere output gegenereerd die wat duidelijker is, negeer de bovenstaande vraag.. ik snap nu waardoor dat komt, zie even mijn vraag helemaal onderaan..

[ Voor 112% gewijzigd door umask op 15-11-2019 23:59 ]

[TweakerNummer]

umask schreef op vrijdag 15 november 2019 @ 21:30:
hoi, ik snap niet precies wat er gebeurt en waarom bepaalde handelingen zijn gekozen om te weten te komen of het een priemgetal is of niet.. zou iemand aub kunnen uitleggen wat de precieze gedachte hierachter is en waarom de code alsnog..
Waarom gebruikt deze persoon bijv. (i/j) in de 2e for loop? en bij modulo staat dat als er geen rest is, dat uit de 2e for loop moet gaan, gaat deze helemaal uit de for loop of alleen de 2e? daarnaast als i = 2 en j = 2 wordt modulo 0, dan gaat die uit de for loop en neem ik aan dat die weer verder gaat met de volgende regels code? maar waarom checkt hij specifiek of j groter is dan het getal dat uit i / j uitkomt?

C#:

int i, j;
         
for (i = 2; i < 100; i++) 
{
   for (j = 2; j <= (i / j); j++) 
   {
      if ((i % j) == 0) break; // if factor found, not prime
   }
   if (j > (i / j)) Console.WriteLine("{0} is prime", i);
}

Hij/zij gebruikt j <= (i / j) in de 2e for loop omdat het werkt (iigv. binnen een bepaald bereik aan invoer). Je kan er ook j = (i / 2) van maken, maar dan krijg je dezelfde resultaten met meerdere executies van de 2e for loop. j = (i / 2) gebruiken maakt het wel begrijpelijker voor mensen:
i = 10 =>
/ 2 test
/ 3 test
/ 4 test
/ 5 test
stop & bepaal of het een priem is.

[ Voor 1% gewijzigd door TweakerNummer op 15-11-2019 23:37 . Reden: Ik zie hij i.p.v. hij/zij! ]

[umask]

Hij/zij gebruikt j <= (i / j) in de 2e for loop omdat het werkt (iigv. binnen een bepaald bereik aan invoer). Je kan er ook j = (i / 2) van maken, maar dan krijg je dezelfde resultaten met meerdere executies van de 2e for loop, maar dat is begrijpelijker voor mensen:
i = 10 =>
/ 2 test
/ 3 test
/ 4 test
/ 5 test
stop & bepaal of het een priem is.

dankjewel dit is nu al wat duidelijker voor me, maar zie mijn andere vraag die nog niet beantwoord is:

Kijk de onderstaande verward me, want hoe kan het dat j bij iteratie 4 dan alsnog 3 wordt, want bij iteratie 3 is het uit de for loop geweest, dus zou die eigenlijk toch bij 2 weer moeten beginnen?

[TweakerNummer]

umask schreef op vrijdag 15 november 2019 @ 23:37:
[...]


dankjewel dit is nu al wat duidelijker voor me, maar zie mijn andere vraag die nog niet beantwoord is:

[...]

Dit komt doordat hoe de for loop in machine code / intermediate code omgezet wordt. Ongeveer zoiets in pseudocode:

x = 0;
#loop_start:
// hier doen we dingen...
x = x + 1;
if (x < 10) #loop_start;
// hier is x 11

Let op: bij een PRIME wordt er dus geen BREAK aangeroepen!

[ Voor 8% gewijzigd door TweakerNummer op 15-11-2019 23:57 ]

[umask]

TweakerNummer schreef op vrijdag 15 november 2019 @ 23:54:
[...]
Dit komt doordat hoe de for loop in machine code / intermediate code omgezet wordt. Ongeveer zoiets in pseudocode:
Let op: bij een PRIME wordt er dus geen BREAK aangeroepen!

vraag 1) hoe bedoel je dat er bij een prime geen break wordt aangeroepen, dit staat geïmplementeerd in de code die ik als voorbeeld had gegeven?
Update: oh zo.. inderdaad, in dit geval niet, omdat het dus anders is aangegeven.

vraag 2) en wat nu voor me in een keer weer onduidelijker is geworden, hoe de for loop bij iteratie zes na de 2e keer eruit komt? dus bij 1e keer is de mod 1, daardoor komt die er niet uit en wordt j opgehoogd. Bij de 2e keer is j 3, dus 7 / 3 = 2 en mod 1, maar de mod voldoet niet aan de controle van de if-statement en alsnog komt die na iteratie 6 eruit en print die 7 is a prime (natuurlijk is 7 een priemgetal, maar hoe kan het in dit geval omdat de logica van de code wat anders zegt..): en hetzelfde gebeurt ook bij iteratie 10, hoe kan het dat die eruit gaat?

code:

for-loop 1, iteration: 1 [i = 2, j = 2] and [cond.: 2 / 2 = 1] and [mod: 2 % 2 = 0]
2 is prime

for-loop 1, iteration: 2 [i = 3, j = 2] and [cond.: 3 / 2 = 1] and [mod: 3 % 2 = 1]
3 is prime

for-loop 1, iteration: 3 [i = 4, j = 2] and [cond.: 4 / 2 = 2] and [mod: 4 % 2 = 0]
4 is not a prime

for-loop 2, iteration: 4 [i = 5, j = 2] and [cond.: 5 / 2 = 2] and [mod: 5 % 2 = 1]
for-loop 1, iteration: 4 [i = 5, j = 3] and [cond.: 5 / 3 = 1] and [mod: 5 % 3 = 2]
5 is prime

for-loop 1, iteration: 5 [i = 6, j = 2] and [cond.: 6 / 2 = 3] and [mod: 6 % 2 = 0]
6 is not a prime

for-loop 2, iteration: 6 [i = 7, j = 2] and [cond.: 7 / 2 = 3] and [mod: 7 % 2 = 1]
for-loop 1, iteration: 6 [i = 7, j = 3] and [cond.: 7 / 3 = 2] and [mod: 7 % 3 = 1]
7 is prime

for-loop 1, iteration: 7 [i = 8, j = 2] and [cond.: 8 / 2 = 4] and [mod: 8 % 2 = 0]
8 is not a prime

for-loop 2, iteration: 8 [i = 9, j = 2] and [cond.: 9 / 2 = 4] and [mod: 9 % 2 = 1]
for-loop 1, iteration: 8 [i = 9, j = 3] and [cond.: 9 / 3 = 3] and [mod: 9 % 3 = 0]
9 is not a prime

for-loop 1, iteration: 9 [i = 10, j = 2] and [cond.: 10 / 2 = 5] and [mod: 10 % 2 = 0]
10 is not a prime

for-loop 2, iteration: 10 [i = 11, j = 2] and [cond.: 11 / 2 = 5] and [mod: 11 % 2 = 1]
for-loop 2, iteration: 10 [i = 11, j = 3] and [cond.: 11 / 3 = 3] and [mod: 11 % 3 = 2]
for-loop 1, iteration: 10 [i = 11, j = 4] and [cond.: 11 / 4 = 2] and [mod: 11 % 4 = 3]
11 is prime

Nog een extra iteratie output waarbij ik zowel vóór de if-statement uitprint, als erná: misschien is dit wat duidelijker

code:

for-loop 1, iteration: 1 [i = 2, j = 2] and [cond.: 2 / 2 = 1] and [mod: 2 % 2 = 0]
2 is prime

for-loop 1, iteration: 2 [i = 3, j = 2] and [cond.: 3 / 2 = 1] and [mod: 3 % 2 = 1]
3 is prime

for-loop 2 - after if, iteration: 3 [i = 4, j = 2] and [cond.: 4 / 2 = 2] and [mod: 4 % 2 = 0]
for-loop 1, iteration: 3 [i = 4, j = 2] and [cond.: 4 / 2 = 2] and [mod: 4 % 2 = 0]
4 is not a prime

for-loop 2 - after if, iteration: 4 [i = 5, j = 2] and [cond.: 5 / 2 = 2] and [mod: 5 % 2 = 1]
for-loop 2 - stuck..., iteration: 4 [i = 5, j = 2] and [cond.: 5 / 2 = 2] and [mod: 5 % 2 = 1]
for-loop 1, iteration: 4 [i = 5, j = 3] and [cond.: 5 / 3 = 1] and [mod: 5 % 3 = 2]
5 is prime

for-loop 2 - after if, iteration: 5 [i = 6, j = 2] and [cond.: 6 / 2 = 3] and [mod: 6 % 2 = 0]
for-loop 1, iteration: 5 [i = 6, j = 2] and [cond.: 6 / 2 = 3] and [mod: 6 % 2 = 0]
6 is not a prime

for-loop 2 - after if, iteration: 6 [i = 7, j = 2] and [cond.: 7 / 2 = 3] and [mod: 7 % 2 = 1]
for-loop 2 - stuck..., iteration: 6 [i = 7, j = 2] and [cond.: 7 / 2 = 3] and [mod: 7 % 2 = 1]
for-loop 1, iteration: 6 [i = 7, j = 3] and [cond.: 7 / 3 = 2] and [mod: 7 % 3 = 1]
7 is prime

for-loop 2 - after if, iteration: 7 [i = 8, j = 2] and [cond.: 8 / 2 = 4] and [mod: 8 % 2 = 0]
for-loop 1, iteration: 7 [i = 8, j = 2] and [cond.: 8 / 2 = 4] and [mod: 8 % 2 = 0]
8 is not a prime

for-loop 2 - after if, iteration: 8 [i = 9, j = 2] and [cond.: 9 / 2 = 4] and [mod: 9 % 2 = 1]
for-loop 2 - stuck..., iteration: 8 [i = 9, j = 2] and [cond.: 9 / 2 = 4] and [mod: 9 % 2 = 1]
for-loop 2 - after if, iteration: 8 [i = 9, j = 3] and [cond.: 9 / 3 = 3] and [mod: 9 % 3 = 0]
for-loop 1, iteration: 8 [i = 9, j = 3] and [cond.: 9 / 3 = 3] and [mod: 9 % 3 = 0]
9 is not a prime

for-loop 2 - after if, iteration: 9 [i = 10, j = 2] and [cond.: 10 / 2 = 5] and [mod: 10 % 2 = 0]
for-loop 1, iteration: 9 [i = 10, j = 2] and [cond.: 10 / 2 = 5] and [mod: 10 % 2 = 0]
10 is not a prime

for-loop 2 - after if, iteration: 10 [i = 11, j = 2] and [cond.: 11 / 2 = 5] and [mod: 11 % 2 = 1]
for-loop 2 - stuck..., iteration: 10 [i = 11, j = 2] and [cond.: 11 / 2 = 5] and [mod: 11 % 2 = 1]
for-loop 2 - after if, iteration: 10 [i = 11, j = 3] and [cond.: 11 / 3 = 3] and [mod: 11 % 3 = 2]
for-loop 2 - stuck..., iteration: 10 [i = 11, j = 3] and [cond.: 11 / 3 = 3] and [mod: 11 % 3 = 2]
for-loop 1, iteration: 10 [i = 11, j = 4] and [cond.: 11 / 4 = 2] and [mod: 11 % 4 = 3]
11 is prime

Update 1: Komt het misschien omdat ondanks dat de binnenste for loop wordt gecheckt, de buitenste alsnog doorgaat zonder te kijken naar de conditie van de modulo operator?

Update 2: ik zie nu door een andere output te gebruiken dat die niet eens in de for loop 2 in gaat bij iteratie 6 en 10?? weet u hoe dat kan.. overal waar false bij staat wilt zeggen dat die erin is geweest, daarom kon ik nu zien dat het programma niet er ingaat, terwijl er wel restanten zijn en de conditie goed is denk ik?:

code:

for-loop 1, iteration: 4 [i = 5, j = 3] and [cond.: 5 / 3 = 1] and [mod: 5 % 3 = 2]
5 is prime

false
for-loop 1, iteration: 5 [i = 6, j = 2] and [cond.: 6 / 2 = 3] and [mod: 6 % 2 = 0]
6 is not a prime

for-loop 1, iteration: 6 [i = 7, j = 3] and [cond.: 7 / 3 = 2] and [mod: 7 % 3 = 1]
7 is prime

false
for-loop 1, iteration: 7 [i = 8, j = 2] and [cond.: 8 / 2 = 4] and [mod: 8 % 2 = 0]
8 is not a prime

false
for-loop 1, iteration: 8 [i = 9, j = 3] and [cond.: 9 / 3 = 3] and [mod: 9 % 3 = 0]
9 is not a prime

false
for-loop 1, iteration: 9 [i = 10, j = 2] and [cond.: 10 / 2 = 5] and [mod: 10 % 2 = 0]
10 is not a prime

for-loop 1, iteration: 10 [i = 11, j = 4] and [cond.: 11 / 4 = 2] and [mod: 11 % 4 = 3]
11 is prime

[ Voor 48% gewijzigd door umask op 16-11-2019 00:49 ]

[TweakerNummer]

umask schreef op vrijdag 15 november 2019 @ 23:59:
[...]

vraag 1) hoe bedoel je dat er bij een prime geen break wordt aangeroepen, dit staat geïmplementeerd in de code die ik als voorbeeld had gegeven?
Update: oh zo.. inderdaad, in dit geval niet, omdat het dus anders is aangegeven.

vraag 2) en wat nu voor me in een keer weer onduidelijker is geworden, hoe de for loop bij iteratie zes na de 2e keer eruit komt? dus bij 1e keer is de mod 1, daardoor komt die er niet uit en wordt j opgehoogd. Bij de 2e keer is j 3, dus 7 / 3 = 2 en mod 1, maar de mod voldoet niet aan de controle van de if-statement en alsnog komt die na iteratie 6 eruit en print die 7 is a prime (natuurlijk is 7 een priemgetal, maar hoe kan het in dit geval omdat de logica van de code wat anders zegt..): en hetzelfde gebeurt ook bij iteratie 10, hoe kan het dat die eruit gaat?
Update: Komt het misschien omdat ondanks dat de binnenste for loop wordt gecheckt, de buitenste alsnog doorgaat zonder te kijken naar de conditie van de modulo operator?

code:

for-loop 1, iteration: 1 [i = 2, j = 2] and [cond.: 2 / 2 = 1] and [mod: 2 % 2 = 0]
2 is prime

for-loop 1, iteration: 2 [i = 3, j = 2] and [cond.: 3 / 2 = 1] and [mod: 3 % 2 = 1]
3 is prime

for-loop 1, iteration: 3 [i = 4, j = 2] and [cond.: 4 / 2 = 2] and [mod: 4 % 2 = 0]
4 is not a prime

for-loop 2, iteration: 4 [i = 5, j = 2] and [cond.: 5 / 2 = 2] and [mod: 5 % 2 = 1]
for-loop 1, iteration: 4 [i = 5, j = 3] and [cond.: 5 / 3 = 1] and [mod: 5 % 3 = 2]
5 is prime

for-loop 1, iteration: 5 [i = 6, j = 2] and [cond.: 6 / 2 = 3] and [mod: 6 % 2 = 0]
6 is not a prime

for-loop 2, iteration: 6 [i = 7, j = 2] and [cond.: 7 / 2 = 3] and [mod: 7 % 2 = 1]
for-loop 1, iteration: 6 [i = 7, j = 3] and [cond.: 7 / 3 = 2] and [mod: 7 % 3 = 1]
7 is prime

for-loop 1, iteration: 7 [i = 8, j = 2] and [cond.: 8 / 2 = 4] and [mod: 8 % 2 = 0]
8 is not a prime

for-loop 2, iteration: 8 [i = 9, j = 2] and [cond.: 9 / 2 = 4] and [mod: 9 % 2 = 1]
for-loop 1, iteration: 8 [i = 9, j = 3] and [cond.: 9 / 3 = 3] and [mod: 9 % 3 = 0]
9 is not a prime

for-loop 1, iteration: 9 [i = 10, j = 2] and [cond.: 10 / 2 = 5] and [mod: 10 % 2 = 0]
10 is not a prime

for-loop 2, iteration: 10 [i = 11, j = 2] and [cond.: 11 / 2 = 5] and [mod: 11 % 2 = 1]
for-loop 2, iteration: 10 [i = 11, j = 3] and [cond.: 11 / 3 = 3] and [mod: 11 % 3 = 2]
for-loop 1, iteration: 10 [i = 11, j = 4] and [cond.: 11 / 4 = 2] and [mod: 11 % 4 = 3]
11 is prime

Nog een extra iteratie output waarbij ik zowel vóór de if-statement uitprint, als erná: misschien is dit wat duidelijker

code:

for-loop 1, iteration: 1 [i = 2, j = 2] and [cond.: 2 / 2 = 1] and [mod: 2 % 2 = 0]
2 is prime

for-loop 1, iteration: 2 [i = 3, j = 2] and [cond.: 3 / 2 = 1] and [mod: 3 % 2 = 1]
3 is prime

for-loop 2 - after if, iteration: 3 [i = 4, j = 2] and [cond.: 4 / 2 = 2] and [mod: 4 % 2 = 0]
for-loop 1, iteration: 3 [i = 4, j = 2] and [cond.: 4 / 2 = 2] and [mod: 4 % 2 = 0]
4 is not a prime

for-loop 2 - after if, iteration: 4 [i = 5, j = 2] and [cond.: 5 / 2 = 2] and [mod: 5 % 2 = 1]
for-loop 2 - stuck..., iteration: 4 [i = 5, j = 2] and [cond.: 5 / 2 = 2] and [mod: 5 % 2 = 1]
for-loop 1, iteration: 4 [i = 5, j = 3] and [cond.: 5 / 3 = 1] and [mod: 5 % 3 = 2]
5 is prime

for-loop 2 - after if, iteration: 5 [i = 6, j = 2] and [cond.: 6 / 2 = 3] and [mod: 6 % 2 = 0]
for-loop 1, iteration: 5 [i = 6, j = 2] and [cond.: 6 / 2 = 3] and [mod: 6 % 2 = 0]
6 is not a prime

for-loop 2 - after if, iteration: 6 [i = 7, j = 2] and [cond.: 7 / 2 = 3] and [mod: 7 % 2 = 1]
for-loop 2 - stuck..., iteration: 6 [i = 7, j = 2] and [cond.: 7 / 2 = 3] and [mod: 7 % 2 = 1]
for-loop 1, iteration: 6 [i = 7, j = 3] and [cond.: 7 / 3 = 2] and [mod: 7 % 3 = 1]
7 is prime

for-loop 2 - after if, iteration: 7 [i = 8, j = 2] and [cond.: 8 / 2 = 4] and [mod: 8 % 2 = 0]
for-loop 1, iteration: 7 [i = 8, j = 2] and [cond.: 8 / 2 = 4] and [mod: 8 % 2 = 0]
8 is not a prime

for-loop 2 - after if, iteration: 8 [i = 9, j = 2] and [cond.: 9 / 2 = 4] and [mod: 9 % 2 = 1]
for-loop 2 - stuck..., iteration: 8 [i = 9, j = 2] and [cond.: 9 / 2 = 4] and [mod: 9 % 2 = 1]
for-loop 2 - after if, iteration: 8 [i = 9, j = 3] and [cond.: 9 / 3 = 3] and [mod: 9 % 3 = 0]
for-loop 1, iteration: 8 [i = 9, j = 3] and [cond.: 9 / 3 = 3] and [mod: 9 % 3 = 0]
9 is not a prime

for-loop 2 - after if, iteration: 9 [i = 10, j = 2] and [cond.: 10 / 2 = 5] and [mod: 10 % 2 = 0]
for-loop 1, iteration: 9 [i = 10, j = 2] and [cond.: 10 / 2 = 5] and [mod: 10 % 2 = 0]
10 is not a prime

for-loop 2 - after if, iteration: 10 [i = 11, j = 2] and [cond.: 11 / 2 = 5] and [mod: 11 % 2 = 1]
for-loop 2 - stuck..., iteration: 10 [i = 11, j = 2] and [cond.: 11 / 2 = 5] and [mod: 11 % 2 = 1]
for-loop 2 - after if, iteration: 10 [i = 11, j = 3] and [cond.: 11 / 3 = 3] and [mod: 11 % 3 = 2]
for-loop 2 - stuck..., iteration: 10 [i = 11, j = 3] and [cond.: 11 / 3 = 3] and [mod: 11 % 3 = 2]
for-loop 1, iteration: 10 [i = 11, j = 4] and [cond.: 11 / 4 = 2] and [mod: 11 % 4 = 3]
11 is prime

Er gebeurt dit bij 7 in for (j = 2; j <= (i / j); j++):

j = 2:
2 <= (7 / 2) -> FALSE

j = 3:
3 <= (7 / 3) -> TRUE

Op dat moment komt hij uit de loop (zonder BREAK dus), en dan wordt PRIME geprint bij j > (i / j):
3 > 7 / 3 -> TRUE

[umask]

TweakerNummer schreef op zaterdag 16 november 2019 @ 00:48:
[...]

Er gebeurt dit bij 7 in for (j = 2; j <= (i / j); j++):

j = 2:
2 <= (7 / 2) -> FALSE

j = 3:
3 <= (7 / 3) -> TRUE

Op dat moment komt hij uit de loop (zonder BREAK dus), en dan wordt PRIME geprint bij j > (i / j):
3 > 7 / 3 -> TRUE

dus terwijl die for loop wordt uitgevoerd, wordt de if-statement ook gecontroleerd, omdat op een gegeven moment het programma ziet dat het true is en automatisch eruit komt? (ook doordat het met name een soort van een globale variabele is? Kan de conditie buiten de for loop gecontroleerd worden en hoeft het niet te blijven hangen in de for loop..?)

Update: oh ja, sorry. ik realiseer me nu dat de for loop niet wordt uitgevoerd, omdat de conditie is: zolang j kleiner is dan wat bij (i / j) uitkomt, pas de for loop moet worden uitgevoerd.. het is hetzelfde als j = 2 <= 1.. eerder kwam dit aan bod, maar heb ik dit even over het hoofd gezien bij deze stap.. maar echt heel erg bedankt!! Allemaal, jullie hebben mij heel erg geholpen, ik waardeer jullie moeite

[ Voor 32% gewijzigd door umask op 16-11-2019 01:06 ]

[TweakerNummer]

umask schreef op zaterdag 16 november 2019 @ 00:55:
[...]

dus terwijl die for loop wordt uitgevoerd, wordt de if-statement ook gecontroleerd, omdat op een gegeven moment het programma ziet dat het true is en automatisch eruit komt? (ook doordat het met name een soort van een globale variabele is? Kan de conditie buiten de for loop gecontroleerd worden en hoeft het niet te blijven hangen in de for loop..?)

[...]

Voor de CPU is er geen for loop, er is slechts machine code. Die for loop wordt dus inderdaad zo uitgevoerd alsof de if-statement steeds gecontroleerd wordt. Denk ook even aan de pseudocode die ik eerder poste. Ik kan helaas de machine code niet laten zien want mijn disassembler in VS is verdwenen.

Het is geen global variabele. Het is een lokale variable die bestaansrecht buiten de for loop heeft omdat hij buiten de for loop gedeclareerd is. Dit valt onder scoping.

code:

            int i = 10;
            {
                Console.WriteLine(i);
            }

            {
                int j = 10;
            }
            Console.WriteLine(j);  // DIT COMPILEERT NIET!

            for (int k = 0; k < 10; k++)
            {
                Console.WriteLine(k);
            }

            for (int l = 0; l < 10; l++)
            {
            }

            Console.WriteLine(l); // DIT COMPILEERT NIET!

[Charango]

umask schreef op vrijdag 15 november 2019 @ 21:30:
Waarom gebruikt deze persoon bijv. (i/j) in de 2e for loop?

Wiskundig gezien is j <= (i / j) hetzelfde als j² <= i of j <= wortel i.

Als i deelbaar is door een natuurlijk getal dat groter is dan de wortel van j (met rest 0), dan is i ook deelbaar door een kleiner getal dan de wortel van j (of door één, maar dat is voor het vinden van priemgetallen niet relevant). Dat kleinere getal zou al eerder in de loop gevonden moeten zijn, dus het heeft geen zin om de loop verder door te laten lopen.

[umask]

TweakerNummer schreef op zaterdag 16 november 2019 @ 01:13:
[...]

Voor de CPU is er geen for loop, er is slechts machine code. Die for loop wordt dus inderdaad zo uitgevoerd alsof de if-statement steeds gecontroleerd wordt. Denk ook even aan de pseudocode die ik eerder poste. Ik kan helaas de machine code niet laten zien want mijn disassembler in VS is verdwenen.

Het is geen global variabele. Het is een lokale variable die bestaansrecht buiten de for loop heeft omdat hij buiten de for loop gedeclareerd is. Dit valt onder scoping.

code:

            int i = 10;
            {
                Console.WriteLine(i);
            }

            {
                int j = 10;
            }
            Console.WriteLine(j);  // DIT COMPILEERT NIET!

            for (int k = 0; k < 10; k++)
            {
                Console.WriteLine(k);
            }

            for (int l = 0; l < 10; l++)
            {
            }

            Console.WriteLine(l); // DIT COMPILEERT NIET!

Ow ja, fout geformuleerd mijn excuses.. dat snap ik alsnog bedankt voor de verduidelijking.

[umask]

Charango schreef op zaterdag 16 november 2019 @ 01:16:
[...]


Wiskundig gezien is j <= (i / j) hetzelfde als j² <= i of j <= wortel j.

Als i deelbaar is door een natuurlijk getal dat groter is dan de wortel van j (met rest 0), dan is i ook deelbaar door een kleiner getal dan de wortel van j (of door één, maar dat is voor het vinden van priemgetallen niet relevant). Dat kleinere getal zou al eerder in de loop gevonden moeten zijn, dus het heeft geen zin om de loop verder door te laten lopen.

Dankjewel voor deze vergelijking, helpt ook erg om een andere formule ervan te maken

[Matis]

Kijk ook eens naar de Wikipedia: Zeef van Eratosthenes
Dat laat precies zien wat hierboven bedoeld wordt.

[Charango]

Matis schreef op zaterdag 16 november 2019 @ 09:34:
Kijk ook eens naar de Wikipedia: Zeef van Eratosthenes
Dat laat precies zien wat hierboven bedoeld wordt.

Hoewel die pagina misschien interessant is is dit wel een andere methode: in de methode waar je naar linkt wordt begonnen met een lijst kandidaten, waarvan vervolgens de niet-priemgetallen verwijderd worden. In de code hierboven wordt per getal i bekeken of het een priemgetal is door te proberen het te delen door alle natuurlijke getallen (behalve 0 en 1) die kleiner zijn dan de wortel van i.

[Matis]

Charango schreef op zaterdag 16 november 2019 @ 11:43:
Hoewel die pagina misschien interessant is is dit wel een andere methode: in de methode waar je naar linkt wordt begonnen met een lijst kandidaten, waarvan vervolgens de niet-priemgetallen verwijderd worden. In de code hierboven wordt per getal i bekeken of het een priemgetal is door te proberen het te delen door alle natuurlijke getallen (behalve 0 en 1) die kleiner zijn dan de wortel van i.

Daar ben ik me van bewust. Met de link probeerde ik aan te geven waarom je maar tot wortel n hoeft te gaan in het geval van een maximum n.
Er zijn meerdere manieren om tot een lijst van priemgetallen te komen.
Zelf ben ik nogal gecharmeerd van de zeef methode.

[Hydra]

@umask hoe bepaal jij op papier of een getal een priemgetal is. Kun jij dat eerst uitleggen?

Matis schreef op zaterdag 16 november 2019 @ 09:34:
Kijk ook eens naar de Wikipedia: Zeef van Eratosthenes
Dat laat precies zien wat hierboven bedoeld wordt.

Hij moet eerst beginnen het met snappen van die brute-force methode. Als 'ie die niet snapt, gaat 'ie die zeef ook niet snappen.

[Daos]

Ik vind die optimalisaties in de code van de topic-start nogal vreemd. Het maakt de code alleen moeilijker te begrijpen en het wordt er niet of nauwelijks sneller op. Wil je sneller priemgetallen vinden dan kan je beter een ander algoritme pakken zoals de eerder genoemde Zeef van Eratosthenes.

Het algoritme uit dit topic zou ik zo opschrijven:

C#:

for (int i = 2; i < 100; i++) 
{
    bool prime = true;

    for (int j = 2; j * j <= i; j++) 
    {
        if ((i % j) == 0) 
        {
            // if factor found, not prime
            prime = false;
            break;
        }
    }

    if (prime)
    {
        Console.WriteLine("{0} is prime", i);
    }
}

[Brilsmurfffje]

Als de TS het beter wil begrijpen kan je beter beginnen met een echte brute force methode en dan manieren bedenken hoe je bepaalde delingen kan overslaan omdat ze dubbel zijn of omdat er geen priem getallen meer verwacht worden.

Pak vervolgens een willekeurige programmeertaal met een debugger en kijk in de debugger mee wat er allemaal in de code gebeurt.

[umask]

Hydra schreef op zaterdag 16 november 2019 @ 15:19:
@umask hoe bepaal jij op papier of een getal een priemgetal is. Kun jij dat eerst uitleggen?

Hij moet eerst beginnen het met snappen van die brute-force methode. Als 'ie die niet snapt, gaat 'ie die zeef ook niet snappen.

vraag 1) wat bedoel je met brute-force methode?

antwoord op uw vraag:
ik bepaal de wortel van een getal en alles daaronder probeer ik te delen met het getal waarvan ik wil weten of het een priemgetal is of niet.. als geen van de getallen deelbaar zijn, dan betekent het een ding: het is deelbaar door zichzelf of door 1, dus dan kom ik er op die manier achter dat het een priemgetal is..

Matis schreef op zaterdag 16 november 2019 @ 09:34:
Kijk ook eens naar de Wikipedia: Zeef van Eratosthenes
Dat laat precies zien wat hierboven bedoeld wordt.

Dat is goed, fijn dat u ook meedenkt. erg bedankt hiervoor.

Daos schreef op zaterdag 16 november 2019 @ 19:37:
Het algoritme uit dit topic zou ik zo opschrijven:

C#:

for (int i = 2; i < 100; i++) 
{
    bool prime = true;

    for (int j = 2; j * j <= i; j++) 
    {
        if ((i % j) == 0) 
        {
            // if factor found, not prime
            prime = false;
            break;
        }
    }

    if (prime)
    {
        Console.WriteLine("{0} is prime", i);
    }
}

Hoi, erg goed dat u een ander voorbeeld hebt gegeven. Uw voorbeeld heeft mij een ander inzicht gegeven om ook tot oplossingen te komen, erg bedankt.

Ik vind die optimalisaties in de code van de topic-start nogal vreemd. Het maakt de code alleen moeilijker te begrijpen en het wordt er niet of nauwelijks sneller op. Wil je sneller priemgetallen vinden dan kan je beter een ander algoritme pakken zoals de eerder genoemde Zeef van Eratosthenes.

Het was een voorbeeld op een site die ik niet begreep en in het begin complex eruitzag, vandaar dat ik daarover een topic startte. Ook u geeft al aan dat het erg moeilijk te begrijpen is, bedankt voor uw begrip en dat is dan echt de reden dat ik deze topic heb gestart. Maar inderdaad er zijn veel mogelijkheden om de priemgetallen te vinden.

[ Voor 55% gewijzigd door umask op 16-11-2019 23:41 ]

[Hydra]

Hier op dit forum hoef je mensen niet met 'u' aan te spreken. Doe maar gewoon 'je'

umask schreef op zaterdag 16 november 2019 @ 23:34:
vraag 1) wat bedoel je met brute-force methode?

Brute force, de meest inefficiente methode, is testen of elk nummer deelbaar is door elk nummer hoger of gelijk aan 2, tot aan de wortel van het getal. Ten eerste kun je dat al veel simpeler doen om de daarvoor bepaalde priemgetallen te bewaren en alleen daar door te delen. Een getal dat deelbaar is door 9 is namelijk ook deelbaar door 3. Een getal dat deelbaar is door 10 is ook deelbaar door 5 en 2.

Daarnaast zijn er zogenoemde 'zeven' zoals de zeef van ratosthenes, algorithmen die deze eigenschap gebruiken om grote delen van je zoekgebied 'weg te strepen'. Hoe hoger de priemgetallen die je wil bepalen hoe belangrijker dit soort implementatiedetails worden.

antwoord op uw vraag:
ik bepaal de wortel van een getal en alles daaronder probeer ik te delen met het getal waarvan ik wil weten of het een priemgetal is of niet.. als geen van de getallen deelbaar zijn, dan betekent het een ding: het is deelbaar door zichzelf of door 1, dus dan kom ik er op die manier achter dat het een priemgetal is..

Precies. En exact dat wil je dus in die for-loops vastleggen. Kun je proberen bovenstaande verhaal aan de verschillende onderdelen van de code in je eerste post koppelen?

[MSalters]

"Brute force" heeft geen precieze wiskundige betekenis. Het betekent simpelweg "zonder slimmigheidjes". @Hydra schrijft dan wel "proberen tot aan de wortel van het getal", maar zelfs dat is beetje slim. Je kunt ook gewoon verder proberen tot de helft van het getal, dat is "nog meer brute force".

Wat ook nog wel eens gedaan wordt is alleen 2 en de oneven getallen proberen. Dat is alweer een klein stapje beter. 4 is dan geen kandidaat meer, maar 9 alsnog wel.

De Zeef van Eratosthenes is de ultieme methode om geen onnodige testen te doen, maar als je voor pure efficiency gaat dan moet je alsnog opletten dat je ook geen onnodige resultaten uitrekent. Als je wil weten of P priem is, dan moet je de Zeef van Eratosthenes gebruiken tot √P, en daarna proberen om P te delen door je priemgetallen kleiner dan √P.