14. februar 2004 - 17:44Der er
47 kommentarer og 1 løsning
Primtals-generator giver fejl-output
Jeg har denne primtals-tjekker, men når jeg kører den, så siger den også, at f.eks. 22 er et primtal... Prøv at bruge den efterfølgende for-løkke...
// Returnerer tværsummen af et tal function tvaersum(tal){ talAry = tal.toString().split(''); var sum = 0; var gammelSum; var started = false; while(gammelSum > 9 || !started) { started = true; for (a = 0; a < talAry.length; a++) { sum += Number(talAry[a]); } talAry = sum.toString().split(''); gammelSum = sum; sum = 0; } return gammelSum; }
//Returnerer false hvis tal ikke er et primtal, og true hvis det er function tjekPrimtal(tal) { var to, tre, fem, syv, primtal = false; var sidsteTal = tal.toString().split(''); sidsteTal = sidsteTal[sidsteTal.length-1];
// Tjek om tallet er deleligt med 2 switch (sidsteTal) { case 2: to = true; break; case 4: to = true; break; case 6: to = true; break; case 8: to = true; break; default: to = false; }
// Tjek om tallet er deleligt med 3 switch (tvaersum(tal)) { case 3: tre = true; break; case 6: tre = true; break; case 9: tre = true; break; default: tre = false; } // Tjek om tallet er deleligt med 5 if (sidsteTal == 0 || sidsteTal == 5) fem = true; else fem = false;
// Tjek om tallet er deleligt med 7 if ((tal/7) == Math.round(tal/7)) syv = true; else syv = false;
if (to || tre || fem || syv) primtal = false; else primtal = true;
//Undtagelser: if (tal == 2 || tal == 3 || tal == 5 || tal == 7) primtal = true; if (tal == 1) primtal = false;
return primtal; }
<script type="text/javascript"> for (b = 0; b <= 100; b++) { if (tjekPrimtal(b)) document.write(b + "<br>"); } </script>
Det er da en besværlig måde du gør det på, denne virker:
<script type="text/javascript"> function primtalscheck(val){ val = +val; if(val%2==0)return false; for(i=3;Math.floor(Math.sqrt(val))>i;i+=2){ if(val%i==0)return false; } return true; } </script>
<form> <input type="text" name="tal"> <button onclick="alert((primtalscheck(this.form.tal.value))?'Det er et primtal':'Det er ikke et primtal')">Check tal</button> </form>
Da primtal over 2 kun kan være ulige udelukker vi lige de lige tal først, og så bruger jeg generelt modulus-funktionen, som returnerer resten ved en division ...
Da en test for primtal kun behøver at gå til kvadratroden af tallet, tester jeg ikke længere end dertil !-)
Et primtal er et tal hvor kun 1 og tallet selv går op i, så det, som skal checkes er, om der findes et tal større end 1 og mindre end tallet, som går op i det uden rest !-)
Da dette tal selvfølgelig skal have et andet tal (som også skal være forskellig fra 1 og tallet selv !-) at blive ganget med (evt. det samme) for at blive tallet, er det kun nødvendigt at checke til _og med_ kvadratroden ...
Eksempel, når vi skal teste 23 udelukker vi først at det er lige, for alle lige tal undtaget 2 er ikke primtal (i hvert fald 2 går op i det !-)
Derefter testes med 3, som giver resten 2 i heltalsdivision (23 modulus 3 er 2), så prøver vi med 5, men da 5 op i 23 er mindre end 5 er der ingen grund til at teste, for vi har udelukket alle muligheder under 5, så 5 vil ikke have et tal at blive ganget med for at give 23 !-)
Tilsvarende med f.eks. 53, som testes med 3 (rest 2), 5 (rest 3), 7 (rest 4) og så ikke mere, for hvis 9 skulle gå op i 53 skulle det ganges med et tal mindre end 9, og dem har vi allerede udelukket !-)
-- det giver selvfølgelig en masse overflødige tests, for at dividere med 9 er overflødigt, for så har vi jo allerede udelukket 3, som også går op i 9, så den ville have fanget den ...
-- men i praksis er den faktisk hurtigere, når vi snakker om de første 100-200 cifre, tror jeg det er !-)
Hvis du bare skal teste et enkelt tal, tror jeg endda det er meget mere, men ellers er taktikken, at man opbygger en database over de primtal, man har fundet ...
En simpel optimering vi være kun at udregne kvadratroden een gang, og putte den i en variabel. I en for-løkke i JavaScript (og Java, og C, og C++) udregnes stopbetingelsen hver gang.
Primtal til kryptografisk brug skal være enormt meget større end disse, og kan ikke findes eller checkes ved en simpel division som denne.
Og endnu mere: stop da forløkken så snart en divisor er fundet, dvs. når ok=true. De fleste tal er ikke primtal. Eller du kan nøjes med at dividere med de kendte primtal, som du allerede har i et array.
Nå ja, du dividerer også kun med primtallene! Så kan det ikke blive bedre. Men det er stadigvik ikke på nogen måde anvendeligt på primtal af kryptografisk størrelse.
-- og så er det godt nok svært at sammenligne med det jeg oplevede, da jeg for 17 år siden fik mulighed for at sætte en basic-rutine til at checke tips-systemer med 9 tegn på en sprit-ny 33 Mhz-maskine ...
for de 3^11 muligheder (177147) tog mange dage !-)
-- og når det var den eneste proces (IE i JS) gav den 87045 med &&ok ...
-- og i c++ giver den vel nærmest en fordobling af effektiviteten, og i assembler kunne man vel lave en rutine, som for alvor udnyttede prefetchen i pIII-processoren !-)
Ja ja, men disse små optimeringer vil stadig ikke komme i nærheden af kryptografiske primtal. Men det er jo slet ikke sikkert spørgeren er interesseret i det ;)
1) Jeg kan OVERHOVEDET ikke følge med i alt det i snakker om. 2) Jo, jeg er interresseret i et kryptografisk primtal, bare for at se hvordan sådan et ser ud. 3) Hvordan ville du skrive et program, erikjacobsen, der ville kunne TJEKKE et kryptografisk primtal, f.eks et på 300 cifre, ca.?
Kan en af jer ikke skrive en artikel om primtals-generatorer og -tjekkere her på E. Den ville nok blive populær, og i hvert fald 5 p. værd, hvis det er på det niveau, i har snakket her... (Og nej, det er ikke for at fedte, det er oprigtigt ment!)
Og hvilke ville det være. Jeg er HELT VILDT interresseret i matematik, og jeg ville sikkert kunne imponere min matematiklærer, hvis jeg lige diskede op med sådan en logaritmisk funktion...
Jeg har skam lært på universitet hvordan man principielt gør. Derfor ved jeg også det er over dit niveau. Og jeg gider ikke finde et program til dig, som du alligevel ikke forstår hvordan virker.
Ærgeligt. Men man har jo dog ikke en morfar der er pensioneret overlærer i fysik-kemi og elektronik, og en mormor der er persioneret overlærer i matematik, dansk og tysk for ingenting, trods alt. Nå, men pyt nu med det...
PS: Men computer har været nede MEGA længe, det er derfor jeg ikke har skrevet... Sory (Ja, med et r).
Er det ikke meget besværligt bare for at finde primtal? ...dether virker: <script type="text/javascript">
//start- og slut-værdier: var i=1 var max=100
//overskrift: document.write("<b>Tal mellem 1 og "+max+":</b><br>")
for (i=i;i<=max;i=i+1) { prim="ja" for (n=2;n<i;n=n+1) { if (i%n==0) { //Denne linie kan tages med hvis man vil have en komplet liste // document.write(i+" er ikke et primtal.<br>") prim="nej" break; } } if (prim=="ja") { document.write("<i>"+i+" er et primtal</i><br>") } } </script>
hm.. ja det har du ret i. den begynder at blive langsom når man kommer over 1.000.000
Synes godt om
Ny brugerNybegynder
Din løsning...
Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.
