[Python] Prime numbers

[flugelisoke]

Ik heb zojuist een opdracht voltooid waarin je een code maakt die prime numbers teruggeeft.

Nu geeft methode 1 een ander resultaat dan methode 2, de else plaatsing. Maar ik zie het gewoon niet, wat er gebeurd waardoor methode 1 wel de goede uitkomst geeft.

Ik ben erg nieuwsgierig waardoor dit precies komt

Methode 1	Methode 2
Python: def IsPrime(num): for i in range(2,num): if num % i == 0: return False else: return True for i in range(1,20): if IsPrime(i + 1): print(i+1,end=" ") print()	Python: def IsPrime(num): for i in range(2,num): if num % i == 0: return False else: return True for i in range(1,20): if IsPrime(i + 1): print(i+1,end=" ") print()

[ Voor 48% gewijzigd door flugelisoke op 25-07-2019 19:39 ]

[omgwtfbbq]

Heb snel even je code nagemaakt, en zie inderdaad hetzelfde gebeuren. wat je hier ontdekt hebt is de for/else loop (http://book.pythontips.com/en/latest/for_-_else.html). Ze gebruiken hier zelfs het voorbeeld van prime numbers

[Room42]

Jij zou deze willen lezen:
http://book.pythontips.com/en/latest/for_-_else.html

En je kunt ook heel makkelijk debuggen door eens een print (met het nummer) voor de return te zetten.

Waarom doe je trouwens i+1 en niet gewoon i?

@flugelisoke Overigens kun jij hier sinds januari 2005 al [code]- of zelfs [code=python]-tags gebruiken om de code leesbaar te plakken.

[ Voor 36% gewijzigd door Room42 op 25-07-2019 19:19 ]

[flugelisoke]

Grappig zeg, die combinatie was ik nog niet eerder tegengekomen, dat verklaard natuurlijk een andere uitkomst

[RobIII]

Als je code post, gebruik dan code tags a.u.b.

[flugelisoke]

RobIII schreef op donderdag 25 juli 2019 @ 19:20:
Als je code post, gebruik dan code tags a.u.b.

Sure, heb het er even ondergezet

[RobIII]

flugelisoke schreef op donderdag 25 juli 2019 @ 19:23:
[...]


Sure, heb het er even ondergezet

Ik was je post inmiddels al aan 't editten

Room42 schreef op donderdag 25 juli 2019 @ 19:15:
@flugelisoke Overigens kun jij hier sinds januari 2005 al [code]- of zelfs [code=python]-tags gebruiken om de code leesbaar te plakken.

Volgens mij is dat al vanaf dag 1 zo. Hooguit dat python syntax highlighting wat later kwam.

[ Voor 46% gewijzigd door RobIII op 25-07-2019 19:27 ]

[Room42]

RobIII schreef op donderdag 25 juli 2019 @ 19:26:
[...]

Ik was je post inmiddels al aan 't editten

Dan is het wel handig om regels 5 en 6 even te benoemen als aandachtsgebied

RobIII schreef op donderdag 25 juli 2019 @ 19:26:
[...]

Volgens mij is dat al vanaf dag 1 zo. Hooguit dat python syntax highlighting wat later kwam.

TS is vanaf januari 2005 geregistreerd, vandaar

[ Voor 35% gewijzigd door Room42 op 25-07-2019 19:28 ]

[DataGhost]

For/else heb je alleen maar iets aan als je break gebruikt. Je gebruikt een directe return dus daarom heeft het helemaal geen toegevoegde waarde en zou je tweede voorbeeld hetzelfde zijn als je de else weghaalt en de return True een tab verder naar links (op de plaats van de else) zet. Om uit te zoeken wat je probleem is moet je toch echt even door je code heen lopen en zelf met het handje uitrekenen wat er gebeurt, en dat vergelijken met wat je verwachtte dat er zou gebeuren en/of of dat klopt met je opzet. Het eerste voorbeeld is gewoon keihard fout.

Edit: je hebt in je TS-edit nu de beide voorbeelden omgedraaid waardoor je stelling dat methode 2 wel klopt fout is.

[ Voor 9% gewijzigd door DataGhost op 25-07-2019 19:29 ]

[flugelisoke]

Ziet er netjes uit @RobIII Thanks!

[RobIII]

Room42 schreef op donderdag 25 juli 2019 @ 19:28:
[...]

Dan is het wel handig om regels 5 en 6 even te benoemen als aandachtsgebied

Hoeveel else'en zie jij in die code dan? Hij geeft toch duidelijk aan dat 't om de else gaat?

Room42 schreef op donderdag 25 juli 2019 @ 19:28:


TS is vanaf januari 2005 geregistreerd, vandaar

Zullen we 't nu weer gewoon ontopic houden?

Waar ik altijd jeuk van krijg is:

code:

if foo
  return true
else
  return false

Waarom niet gewoon:

code:

return foo

Of, in jouw geval dus:

Python:

return num % i != 0

[ Voor 38% gewijzigd door RobIII op 25-07-2019 19:31 ]

[flugelisoke]

RobIII schreef op donderdag 25 juli 2019 @ 19:28:
[...]

Hoeveel else'en zie jij in die code dan? Hij geeft toch duidelijk aan dat 't om de else gaat?

[...]




Zullen we 't nu weer gewoon ontopic houden?

Waar ik altijd jeuk van krijg is:

code:

if foo
  return true
else
  return false

Waarom niet gewoon:

code:

return foo

Of, in jouw geval dus:

Python:

return num % i != 0

In dat laatste geval "return num % i != 0" klopt de prime berekening niet meer hier, hij slaat 2 over en wanneer ik de range 0,20 verander in bijvoorbeeld 200, komen er getallen in de lijst te staan die geen prime numbers zijn.

Al ziet die code van je er wel strak en clean uit.

Dus in dit geval lekker blijven krabben

[ Voor 3% gewijzigd door flugelisoke op 25-07-2019 19:35 ]

[RobIII]

flugelisoke schreef op donderdag 25 juli 2019 @ 19:35:
Dus in dit geval lekker blijven krabben

Heb je ook de == veranderd in != ?

[flugelisoke]

RobIII schreef op donderdag 25 juli 2019 @ 19:40:
[...]

Heb je ook de == veranderd in != ?

Jep, heb de hele code overgenomen.

[RobIII]

Euh, je originele code werkt evenmin? Je IsPrime is niets anders dan een IsOdd (of IsEven)? Of ben ik nou bevangen door de hitte?

[ Voor 4% gewijzigd door RobIII op 25-07-2019 19:44 ]

[flugelisoke]

RobIII schreef op donderdag 25 juli 2019 @ 19:43:
Euh, je originele code werkt evenmin? Je IsPrime is niets anders dan een IsOdd (of IsEven)? Of ben ik nou bevangen door de hitte?

Niet perse, het gaat juist om hoe je een priemgetal kunt onderscheiden van de overige getallen, het is een prime als het getal enkel door zichzelf deelbaar is en door 1, niets anders.

Zo is 9 geen priemgetal, terwijl 9 wel in die code uitkomt.

9 is deelbaar door 2 (bedankt @PageFault ), door 9, maar ook door 3.

[ Voor 3% gewijzigd door flugelisoke op 26-07-2019 09:16 ]

[Daos]

Methode 1 is juist, niet Methode 2. Omdat de for-loop met 2 begint kijkt die inderdaad alleen of het even of oneven is.

[Room42]

RobIII schreef op donderdag 25 juli 2019 @ 19:43:
Euh, je originele code werkt evenmin? Je IsPrime is niets anders dan een IsOdd (of IsEven)? Of ben ik nou bevangen door de hitte?

Kan zijn dat ik het nu verkeerd zie maar volgens mij gaat jouw voorstel alleen werken in de niet-werkende code:

Python:

def IsPrime(num):
    for i in range(2,num):
        return num % i != 0

for i in range(1,20):
    if IsPrime(i + 1):
            print(i+1,end=" ")

In de werkende code, zul je altijd die if nodig hebben omdat ie anders de for-loop niet doorloopt.

Python:

def IsPrime(num):
    for i in range(2,num):
        return num % i != 0
    else:
        return True


for i in range(1,20):
    if IsPrime(i + 1):
            print(i+1,end=" ")

Dat moet dus zijn:

Python:

def IsPrime(num):
    for i in range(2,num):
        if num % i == 0:
            return False
    else:
        return True


for i in range(1,20):
    if IsPrime(i + 1):
            print(i+1,end=" ")

[Daos]

De theorie: Een priem-getal is een getal dat alleen deelbaar is door 1 of zichzelf.

Wat de juiste code doet is in een for-loop alle waardes proberen van 2 tot de waarde die je meegeeft aan de functie. Zodra iets deelbaar is (= remainder is 0) dan is het geen priem-getal. Lukken alle tests dan is het wel een priem-getal.

[RobIII]

flugelisoke schreef op donderdag 25 juli 2019 @ 19:46:

Niet perse, het gaat juist om hoe je een priemgetal kunt onderscheiden van de overige getallen, het is een prime als het getal enkel door zichzelf deelbaar is en door 1, niets anders.

Zo is 9 geen priemgetal, terwijl 9 wel in die code uitkomt.

9 is deelbaar door 2, door 9, maar ook door 3.

Ik weet wat een priemgetal is en hoe je 't berekent Maar ik lag mobiel te frotten en staarde naar "Methode 2"

[flugelisoke]

RobIII schreef op donderdag 25 juli 2019 @ 20:12:
[...]

Ik weet wat een priemgetal is en hoe je 't berekent Maar ik lag mobiel te frotten en staarde naar "Methode 2"

Oke, ik dacht even dat je de context niet begreep.

[SinergyX]

Nu ben ik hobbymatig soms wat bezig in Python, veelal gewoon copy/paste code en beetje aankloten, maar is 1 van de weinige talen waar een precieze plaatsing van een Else impact heeft bij een If en For loop?

[DataGhost]

Nee, de else bij de for is gewoon syntactic sugar voor "if geen break gedaan in de loop" en het is "toeval" dat het hier werkt.

code:

found = False
for a in b:
    if a:
        found = True
        break
if not found:
    return False
doe_iets()

en

code:

for a in b:
    if a:
        break
else:
    return False
doe_iets()

is hetzelfde. De "plaatsing van de else" maakt evenveel uit als de plaatsing van een } in C of aanverwante talen. In mijn laatste voorbeeld hoort de else bij de for, als je 'm een tab dieper zet hoort 'ie bij de if. In het geval van de TS kan de else weg, voor het resultaat maakt het niks uit, want er staat uberhaupt geen break in de loops van de TS.

[ Voor 8% gewijzigd door DataGhost op 25-07-2019 20:27 ]

[PageFault]

flugelisoke schreef op donderdag 25 juli 2019 @ 19:46:
[...]


Niet perse, het gaat juist om hoe je een priemgetal kunt onderscheiden van de overige getallen, het is een prime als het getal enkel door zichzelf deelbaar is en door 1, niets anders.

Zo is 9 geen priemgetal, terwijl 9 wel in die code uitkomt.

9 is deelbaar door 2, door 9, maar ook door 3.

9 delen door 2 geeft geen geheel getal.

[flugelisoke]

PageFault schreef op vrijdag 26 juli 2019 @ 09:05:
[...]


9 delen door 2 geeft geen geheel getal.

Natuurlijk

De warmte!

[PageFault]

flugelisoke schreef op vrijdag 26 juli 2019 @ 09:14:
[...]


Natuurlijk

De warmte!

Nou ja, je beweerde dat 9 deelbaar is door 2 en dat is wiskundig correct. Alleen voor priemgetallen zou het dan op een geheel getal uit moeten komen

Ik vraag me af waarom je niet sneller de priemgetallen zou willen vinden door te "zeven" ("zeef van Eratosthenes").

[Room42]

PageFault schreef op vrijdag 26 juli 2019 @ 12:03:
[...]

Ik vraag me af waarom je niet sneller de priemgetallen zou willen vinden door te "zeven" ("zeef van Eratosthenes").

Volgens mij was het vinden van de priemgetallen niet het doel maar een middel.

[PageFault]

Room42 schreef op vrijdag 26 juli 2019 @ 12:06:
[...]

Volgens mij was het vinden van de priemgetallen niet het doel maar een middel.

Waarschijnlijk is deze case ook veel leerzamer geweest op deze manier, door het subtiele indent verschilletje krijg je een heel ander resultaat

[CCJJVV]

Kleine optimalisatie:

Een keer door 2 delen en vervolgens enkel over de oneven getallen lopen door bij 3 te beginnen en vervolgens elke iteratie +2 te doen?

[Daos]

CCJJVV schreef op vrijdag 26 juli 2019 @ 12:25:
Kleine optimalisatie:

Een keer door 2 delen en vervolgens enkel over de oneven getallen lopen door bij 3 te beginnen en vervolgens elke iteratie +2 te doen?

Dat heeft nog steeds dezelfde complexiteit van O(N). Wat iets beter werkt is loopen tot en met de wortel van het nummer.

edit:
Om even het verschil aan te geven: neem bijvoorbeeld 1000003 (ongeveer een miljoen). Het algoritme uit dit topic heeft hiervoor een miljoen iteraties nodig. Jouw versie een half miljoen. Dat is dezelfde orde van grootte. Neem je mijn versie, dan heb je maar iets van duizend iteraties nodig. Dat is wel een wereld van verschil (er bestaan nog veel snellere algoritmes)

[ Voor 32% gewijzigd door Daos op 26-07-2019 22:43 ]

[Ben(V)]

Even een paar opmerkingen.

• Methode 2 is gewoon fout.
• In methode 1 kan die else gewoon weg en de return True op het for level
• Als je dit wilt gebruiken vanaf het getal 1 gaat het ook fout
• Het print statement werkt uiteraard niet

Het zou zoiets moeten zijn:

Python:

def IsPrime(num):
    for i in range(2,num):
        if not num % i:
            return False
    return False if num == 2 else True

for i in range(1,20):
    if IsPrime(i):
            print i
print()

[Matis]

Persoonlijk vind ik de Wikipedia: Zeef van Eratosthenes een hele mooie, begrijpbare en snelle manier van alle priemgetallen tot X te berekenen.

[ThomasG]

Matis schreef op maandag 5 augustus 2019 @ 18:44:
Persoonlijk vind ik de Wikipedia: Zeef van Eratosthenes een hele mooie, begrijpbare en snelle manier van alle priemgetallen tot X te berekenen.

Dan moet je ook even naar de Wikipedia: Sieve of Atkin (Zeef van Atkin) kijken, want die is (theoretisch) net iets efficiënter.

[Matis]

ThomasG schreef op maandag 5 augustus 2019 @ 18:49:
Dan moet je ook even naar de Wikipedia: Sieve of Atkin (Zeef van Atkin) kijken, want die is (theoretisch) net iets efficiënter.

Ook die ken ik, maar vind ik persoonlijk wat minder mooi en (voor een beginner althans) een heel stuk minder begrijpbaar. Vandaar dat ik eerdergenoemde voorstelde