[TI basic] priemgetaltest

[Verwijderd]

Ik heb zelf al meerdere programma's gemaakt in TI-basic. (voor op m'n rekenmachine) Momenteel probeer ik een priemgetal test te maken. Het werkte, dus heb ik het geoptimaliseerd. Toen ik de bug constateerde, heb ik hem omgebouwt om te kijken waar het zit.

De fout treed op wanneer ik 35 invul. Verder heb ik nog geen getal gevonden dat ook niet klopt. Veel getallen die eindigen op 5 getest, en tafel van 7. Maar niets.

code:

prompt n                      //vraagt om het getal dat getest moet worden
abs(iPart(N->N             //neemt de absolute waarde, en neemt alleen het gehele deel
2->B                           //nodig voor verder in mijn programma
Pause N                     //bugtestfeature, laat even pauzeren. Hij haalt deze pauze, N is 35
if sum(N={1,2,3,5,7      //Als N of 1 of 2 of 3 of 5 of 7 is, is dit 1, en gaan we dus door
then                           
Disp sum(N={1,2,3,5,7 //Laat nog maar even zien of mijn test eerder klopt, geeft 0 aan
Pause N                     //pauzeert, jawel, N is nog steeds 35
goto 1                        // ga naar het lbl 1
else
..........
lbl 1
Dips "Ja                       //het is een priemgetal (maar 35 is het niet!)

oftwel, waarom passeert de test bij 35 wel de if, ondanks dat het 0 aangeeft, en anders nooit?

[remco_k]

Ik zie een andere bug:
1 is geen priemgetal.

Verder snap ik de ballen van deze syntax:

code:

if sum(N={1,2,3,5,7

Ik ken wat Basic, veel C++ en wat PHP, maar dit heb ik nog nooit gezien.
(en die 1 moet eruit... )
Misschien moet die 'then' er perse achter staan wil het werken?

Probeer het gebruik van goto te vermijden. Daarbij is de goto op regel 9 overbodig.

En natuurlijk moet je niet controleren tegen een array van priemgetallen die je vooraf invoert, je moet het gaan berekenen.

[ Voor 39% gewijzigd door remco_k op 30-01-2009 20:00 ]

[Verwijderd]

ik weet dat 1 geen priemgetal is, maar als je 1 niet doet, krijg ik later in m'n code problemen. Bovendien ben je een mong$$l als je 1 in vult (het programma wordt vooral gebruikt voor in priemfactoren ontbinden.

code:

if sum(N={1,2,3,5,7

betekent dat hij de lijst {1,2,3,5,7} test, dus kijkt of ze gelijk zijn aan N. De output is een lijst, bijvoorbeeld {0,0,0,1,0} als N 5 is. Omdat if geen lijsten aankan, neemt hij de som ervan, dus sum(.

edit:

en dit doe ik omdat ik daarna ga ik kijken wat het laatste getal is, maar die test faalt bij getallen van 1 cijfer lang. programmeren in TI-basic is soms wat omslachtig.

[ Voor 16% gewijzigd door Verwijderd op 30-01-2009 20:06 ]

[remco_k]

Oke, dus als je 35 invult komt uit deze code:

code:

sum(N={1,2,3,5,7

Het antwoord 0.
Dat betekend dus dat je if statement niet (goed) werkt. Misschien moet je zoiets specifieker doen:

code:

if 1=sum(N={1,2,3,5,7

Geen idee of de syntax klopt, als je de strekking maar begrijpt.

[Verwijderd]

nou, geen idee wat er mis was, maar ik heb de hele if opnieuw getypt. Nu werkt het rare zaak.

in ieder geval bedankt.

[remco_k]

Misschien de , tussen de 3 en de 5 vergeten?

[Verwijderd]

achteraf gezien, zou dat best mogelijk zijn. Maar ik heb het zovaak gechecked, dat dat wel raar zou zijn. Misschien komt dat precies op de volgende regel. He, dat zou wel stom zijn zeg

[zwippie]

Verwijderd schreef op vrijdag 30 januari 2009 @ 20:17:
nou, geen idee wat er mis was, maar ik heb de hele if opnieuw getypt. Nu werkt het rare zaak.

in ieder geval bedankt.

Je weet dat er een compactere manier is om te bepalen of een getal een priemgetal is?
(Die niet perse sneller hoeft te zijn want zeer naief)

Ik heb natuurlijk niet al je code gezien maar ik denk dat je hier eigenlijk net iets te moeilijk doet. Wat zegt je programma nu bijvoorbeeld als je als input 271 geeft?

[Verwijderd]

dan zegt het in 3 seconde dat het een priem is. Ik zal dan maar even de volledige code meegeven:

code:

prompt n
abs(iPart(N->N         //niet negatief, en geheel getal
if sum(N={1,2,3,5,7 //ja, ik weet het, 1 is geen priem ;)
goto 1                     //goto gaat naar gelijknamige label
10fPart(N/10->C       //laatste cijfer is
2->B
if sum(C={0,2,4,5,6,8 //als N even of deelbaar door 5
goto 2 
1+iPart(N/2->C
For(B,3,C,2             //variabele, beginwaarde, eindwaarde, toename
if not(fpart(N/B         //not( maakt als het 0 geeft er 1 van.
goto 2
end                          //terug naar For
lbl 1
Disp "JA
stop
lbl 2
B+3(C=5)                 //voor ontbinden in factoren, zorgt dat als het getal deelbaar door 5 is, B verandert wordt.
Disp "Nee",Ans,N/Ans  //Ans is de vorige regel, elke ',' is een enter en ook dit is voor ontbinden in priemfactoren

[zwippie]

Verwijderd schreef op vrijdag 30 januari 2009 @ 21:28:
dan zegt het in 3 seconde dat het een priem is. Ik zal dan maar even de volledige code meegeven:

Ok, ik ken de syntax van TI basic niet, en het was misschien ook niet het handigste voorbeeld. Wat zegt ie van 143, 7793, 13519 en 62429?

Als je methode werkt, dan werkt ie hoor. Verder heb ik geen idee van de snelheid van zo'n apparaat, ben nu wel benieuwd eigenlijk. Maar als dit je code is om te bepalen of een getal een priemgetal is, dan denk ik dat er eventueel een eenvoudigere manier is.

[Verwijderd]

144=11*13 in 700 ms
7793 gaf na 5 minuten nog niet aan dat het priem was. de variabele B was toen bij 2565, en moest dus nog 3897-2565=1332 keer tikken.
13519 = 11 * 1229 in 700 ms
62429 = 163 * 383 in 4,5 s.

de methode werkt, maar het kan vast wel iets beter voor grote priemgetallen haha. Het is alleen lekker korte en kleine code. Maar aanvulling/aanpassingen op het algoritme zijn welkom! ook gewoon in tekst, bij gebrek aan kennis van TI-basic

[zwippie]

Ow, je bent aan het ontbinden in priemfactoren.
Je had het over een priemgetaltest, dus ik ging er vanuit dat je alleen wou checken of een getal een priemgetal is.

[remco_k]

Tot een paar minuten geleden dacht ik dat ook, gezien het onderwerp van het topic.

[Soultaker]

Ook bij ontbinden van priemgetallen kun je stoppen zodra je potentiele factor groter dan de wortel van je (resterende) getal is hoor. Met dat principe zou je ook in TI BASIC getallen tot ongeveer een miljoen snel moeten kunnen factorizeren...

Python:

def factors(n):
  res = []
  p = 2
  while p*p <= n:
    while n%p == 0:
      res.append(p)
      n /= p
    p += 1
  if n > 1: res.append(n)
  return res

(Nog voor optimalisatie vatbaar; b.v. 2en eerst doen, en daarna alleen oneven getallen nagaan.)

[Verwijderd]

Nou, het is een priemgetallen test, die ik alleen wel ook gebruik om te ontbinden in priemfactoren. Hij zou dus multifunctioneel moeten zijn

Ik ben dan weer niet zo goed met python. Snap niet helemaal wat je wilt. Maar ik zou m'n code graag zo multifunctioneel houden. Dus, zowel priemgetaltest als ontbinden in factoren. Maar als je zegt dat ontbinden in factoren op een andere manier sneller kan? Misschien moet ik er dan een apart programma voor maken.

[Ivo]

Als je hebt ontbonden in priemfactoren is de priemgetaltest sowieso triviaal, dus die multifunctionaliteit heb je altijd wel. Soultaker's code doet het volgende:
Voor elk getal 2 <= p <= sqrt(n), voeg p toe aan de resultaten en deel n door p zolang p een deler is van n. Aan het einde wordt nog gekeken of er een priemfactor overbleef of 1.

Edit: Je mag er nog over nadenken waarom je alleen priemfactoren uitdeelt en geen andere waarden. Dit valt niet af te leiden uit mijn samenvatting.

[ Voor 18% gewijzigd door Ivo op 31-01-2009 14:41 ]

[Verwijderd]

Ik snap waarom je alleen priemgetallen uitdeelt natuurlijk. Daar maakt zelfs mijn programma gebruik van. Ik zal er is naar kijken. Bedankt.

[Soultaker]

Ivo schreef op zaterdag 31 januari 2009 @ 14:38:
Soultaker's code doet het volgende: Voor elk getal 2 <= p <= sqrt(n), voeg p toe aan de resultaten en deel n door p zolang p een deler is van n. Aan het einde wordt nog gekeken of er een priemfactor overbleef of 1.

Klopt helemaal, maar bedenk wel dat in mijn lus n niet constant is. Daardoor kun je grote getallen die geen grote priemfactoren hebben snel factoriseren. (Als n in het begin al een priemgetal is, maakt het niet uit.) De grootste priemfactor van n is bepalend voor hoe lang het factoriseren duurt, niet n zelf.

Zoals gezegd zijn er nog wel wat dingen aan te optimaliseren (elke keer dat kwadraat uitrekenen is niet handig bijvoorbeeld), wat het leukste is om zelf uit te zoeken. Maar zelfs zonder allerlei trucs zou zo'n soort aanpak wel redelijk efficient moeten werken.

[ Voor 25% gewijzigd door Soultaker op 31-01-2009 18:11 ]

[Confusion]

Je hoeft zelfs niet alle oneven getallen te testen: priemgetallen zijn altijd van de vorm 6n-1 of 6n+1 voor n > 0.

[wackmaniac]

Confusion schreef op zaterdag 31 januari 2009 @ 20:10:
Je hoeft zelfs niet alle oneven getallen te testen: priemgetallen zijn altijd van de vorm 6n-1 of 6n+1 voor n > 0.

Moet dit niet zijn voor n > 3? 2 en 3 zijn priem en voldoet niet aan 6n-1 (mininmaal 5) of 6n+1 (mininmaal 7)

[Verwijderd]

Ja, maar in onze huidige beschaving is het geen vraag meer op 2 en 3 priem zijn (ik bedoel te zeggen dat deze regel alleen van nu is voor grote getallen).

En als toevoeging op bovenstaande regel: priemgetallen eindigen niet op 5 (behalve 5 zelf).

[ Voor 54% gewijzigd door Verwijderd op 01-02-2009 00:47 ]

[Confusion]

wackmaniac schreef op zondag 01 februari 2009 @ 00:11:
Moet dit niet zijn voor n > 3? 2 en 3 zijn priem en voldoet niet aan 6n-1 (mininmaal 5) of 6n+1 (mininmaal 7)

Als je het leest als
"(priemgetallen zijn altijd van de vorm 6n-1 of 6n+1) voor n > 0."
in plaats van als
"priemgetallen zijn altijd van de vorm (6n-1 of 6n+1 voor n > 0)."
dan is het impliciet dat het alleen voor priemgetallen vanaf 5 geldt.

[Ivo]

Verwijderd schreef op zaterdag 31 januari 2009 @ 14:59:
Ik snap waarom je alleen priemgetallen uitdeelt natuurlijk. Daar maakt zelfs mijn programma gebruik van. Ik zal er is naar kijken. Bedankt.

Ik had weinig zin om TI Basic te gaan ontcijferen. Mijn excuses daarvoor.

Klopt helemaal, maar bedenk wel dat in mijn lus n niet constant is. Daardoor kun je grote getallen die geen grote priemfactoren hebben snel factoriseren. (Als n in het begin al een priemgetal is, maakt het niet uit.) De grootste priemfactor van n is bepalend voor hoe lang het factoriseren duurt, niet n zelf.

Ja, maar impliciet test je dus 2 <= p <= sqrt(n). Je algoritme is enkel slim genoeg om op een gegeven moment te weten dat er geen priemfactoren meer over zijn.

[Verwijderd]

Confusion schreef op zaterdag 31 januari 2009 @ 20:10:
Je hoeft zelfs niet alle oneven getallen te testen: priemgetallen zijn altijd van de vorm 6n-1 of 6n+1 voor n > 0.

Ik denk dat de geleerde die op zoek zijn naar nieuwe grotere priemgetallen heel blij zullen zijn met jou formule...daar zijn ze al vrij lang naar op zoek zegmaar.

Maar helaas bestaat er geen formule waar je een willekeurige N in kan stoppen die dan pats boem een priemgetal uitpoept...was het maar zo makkelijk.

[Verwijderd]

Verwijderd schreef op zondag 01 februari 2009 @ 13:31:
[...]

Ik denk dat de geleerde die op zoek zijn naar nieuwe grotere priemgetallen heel blij zullen zijn met jou formule...daar zijn ze al vrij lang naar op zoek zegmaar.

Maar helaas bestaat er geen formule waar je een willekeurige N in kan stoppen die dan pats boem een priemgetal uitpoept...was het maar zo makkelijk.

Ten eerste zegt hij dat niet en ten tweede heeft hij gelijk
Zoek maar eens wat eigenschappen van priemgetallen op.

[ Voor 5% gewijzigd door Verwijderd op 01-02-2009 13:34 ]

[Soultaker]

Verwijderd schreef op zondag 01 februari 2009 @ 13:31:
Maar helaas bestaat er geen formule waar je een willekeurige N in kan stoppen die dan pats boem een priemgetal uitpoept...was het maar zo makkelijk.

f(n) = 7
Zoiets?

[lvh]

Verwijderd schreef op zondag 01 februari 2009 @ 13:31:
[...]

Ik denk dat de geleerde die op zoek zijn naar nieuwe grotere priemgetallen heel blij zullen zijn met jou formule...daar zijn ze al vrij lang naar op zoek zegmaar.

Maar helaas bestaat er geen formule waar je een willekeurige N in kan stoppen die dan pats boem een priemgetal uitpoept...was het maar zo makkelijk.

Hij zegt dat alle priemgetallen van de vorn 6N+/-1 zijn -- da's heel wat anders dan zeggen dat alle zulke getallen priem zijn. Alle appelsienen zijn rond, maar niet alles wat rond is is een appelsien

[Verwijderd]

Oh ja shit, mijn foutje...sorry. Maar dan moet je dus alsnog voor elk getal wat aan die regel voldoet op een andere manier (uitrekenen dus) controleren of het een priem is.

[Voutloos]

En dat zei confusion ook. Het is enkel een optimalisatie waarmee je toch redelijk wat tests kan overslaan.

[Verwijderd]

Verwijderd schreef op zondag 01 februari 2009 @ 13:31:
[...]

Ik denk dat de geleerde die op zoek zijn naar nieuwe grotere priemgetallen heel blij zullen zijn met jou formule...daar zijn ze al vrij lang naar op zoek zegmaar.

Maar helaas bestaat er geen formule waar je een willekeurige N in kan stoppen die dan pats boem een priemgetal uitpoept...was het maar zo makkelijk.

code:

n² - 79n + 1601 voor 0<=n<=79

Er is er ook een voor 0<=n<=39. Of ze er ook zijn voor grotere priemgetallen, geen idee, zover heb ik me er nooit in verdiept.

[Verwijderd]

Ik wil jullie natuurlijk niet mijn uiteindelijk versies onthouden. Ik heb 2 programma's gemaakt, 1 voor priemgetallen ontbinden, 1 priemgetallen test.

Ti-basic:

code:

"by ...
prompt n
abs(ipart(N->N
if sum(N={1,2,3,5
goto 1
10fpart(N/10
if sum(ans={0,2,,4,5,6,8
goto 2
For(B,3,1+ipart(&#8730(N)),2
If not(fPart(N/B
goto 2
end
lbl 1
Disp "ja
stop
lbl 2
Dips "nee

en het ontbinden:

Ti-basic:

code:

"by ...
prompt N
For(A,2,1+iPart(&#8730(N)
If not(fpart(N/A
then
Disp A
N/A->N
A-1->A
if N=1
Stop
End
End
If N>1
Disp N

Uitleg op aanvraag

[Soultaker]

Met &#8730 bedoel je √ neem ik aan? Overigens is 1 is nog steeds geen priemgetal.

De check of N even is, kan vast beter. TI BASIC heeft toch wel een modulo functie? Desnoods test je of N/2 een geheel getal is (if fpart(N/2)=0 goto 2 ofzo), dat is nog beter dan 10*(fpart(N/10)) vergelijken met 0, 2, 4, 6 en 8 (wat je nu doet).

[ Voor 24% gewijzigd door Soultaker op 17-02-2009 17:42 . Reden: ik kan niet schrijven vandaag ]

[Verwijderd]

Ja, ik bedoelde het wortel teken ja:D

De check of N even is kan wel beter, maar als je ook op 'laatste getal is 5' wil checken, is dit de meest snelle en korte methode.

[Soultaker]

Dat checken op deelbaarheid door 5 doe je toch al in de tweede iteratie van je for-lus; daar zou ik persoonlijk niet voor optimaliseren, maar ok.

Trouwens, waarom heb je daar ook een 3 bij staan?! Getallen die eindigen op 3 (neem: 3, of 13) kunnen wel priemgetallen zijn!

[ Voor 30% gewijzigd door Soultaker op 17-02-2009 18:26 ]

[Verwijderd]

dat is een typfout. Dank voor je oplettendheid.

Opzich heb je wel een punt. Hieronder de herschreven versie:

Oja, het ontbinden doe ik met een for-lus omdat die veel sneller is.voordat iemand zegt dat while makkelijker zou zijn.

code:

"by ...
prompt n
abs(ipart(N->N
if sum(N={1,2,3,5
goto 1
if not(fpart(N/2
goto 2
For(B,3,1+ipart(√(N)),2
If not(fPart(N/B
goto 2
end
lbl 1
Disp "ja
stop
lbl 2
Dips "nee

[ Voor 46% gewijzigd door Verwijderd op 17-02-2009 18:52 ]

[siddler]

Verwijderd schreef op dinsdag 17 februari 2009 @ 18:48:
dat is een typfout. Dank voor je oplettendheid.

Opzich heb je wel een punt. Hieronder de herschreven versie:

Oja, het ontbinden doe ik met een for-lus omdat die veel sneller is.voordat iemand zegt dat while makkelijker zou zijn.

code:

"by ...
prompt n
abs(ipart(N->N
if sum(N={1,2,3,5
goto 1
if not(fpart(N/2
goto 2
For(B,3,1+ipart(√(N)),2
If not(fPart(N/B
goto 2
end
lbl 1
Disp "ja
stop
lbl 2
Dips "nee

Neem aan dat in die laatste regel code het ook Disp moet zijn toch?

[HuHu]

Het hoeft niet op een TI, maar het zou netjes zijn als je de sluit-haakjes ook in je code zet. Dus niet zo:

code:

abs(ipart(N->N

maar zo:

code:

abs(ipart(N->N))

Puur voor de leesbaarheid en wellicht kan het soms helpen om fouten eerder te vinden.

[doeternietoe]

HuHu schreef op dinsdag 17 februari 2009 @ 22:24:
Het hoeft niet op een TI, maar het zou netjes zijn als je de sluit-haakjes ook in je code zet. Dus niet zo:

code:

abs(ipart(N->N

maar zo:

code:

abs(ipart(N->N))

Puur voor de leesbaarheid en wellicht kan het soms helpen om fouten eerder te vinden.

Geheugenbesparing

Bij ons op school heb ik heel wat programma's in TI-basic geproduceerd zien worden waarbij zoveel mogelijk haakjes werden weggelaten.

[Verwijderd]

Ja, inderdaad geheugenbesparing. Ik maak ze eerst met, en optimaliseer later.

vandaag nog even uitgewerkt. Het is nu dit (wel weer groter geworden, maarja)

code:

"By ...
Prompt N
abs(N->N
If fPart(N)=!0
goto 2
if iPart(N/e10
then
Disp "Te groot
stop
If sum(N={1,2,3,5,7
goto 1
If not(fPart(N/2
goto 2
If not(fPart(N/3
goto 2
int(1+√N                        //1+ de wortel van N
For(B,6,ANS,6
If not(fPart(N/(B-1
goto 2
If not(fPart(N/B+1
goto 2
End
lbl 1
Disp "Ja
Stop
lbl 2
Disp "Nee

maar volgens mij zit er nog een bug in. Moet hem even vinden

edit1: en gevonden.

edit2:
Een kleine 'benchmark'. Het 100008ste priemgetal, 1,299,827, kost hem 40 seconden

Geoptimaliseerd, nu kost hetzelfde priemgetal hem 20 seconden

code:

int(1+wortel(N)
For(B,6,Ans,6
If not(fpart(N/(b-1))) or not(fpart(N/(b+1)))
goto 2
end

edit3:

code:

int(1+wortel(N)
For(B,6,Ans,6
N
If not(fpart(Ans/(b-1))) or fpart(Ans/(b+1
goto 2
end

Alles kan sneller, nu 13 seconden.

edit4: hmm, 13 sec had een bug volgens mij. Nu hij eruit is is hij weer langzamer. Ach ja.

[ Voor 44% gewijzigd door Verwijderd op 18-02-2009 20:49 ]