Primtallkalkulator

[Raincloud]

Hei, har laget en primtallkalkulator som også vil primtallsfaktorisere. Du finner den på http://www.primtall.com . Hva synes dere, evnt forslag til nye funksjoner? Har planer om å lage en funksjon som finner alle primtall mellom X og Y, f.eks. du skriver inn 400 og 1000, så popper alle primtall mellom 400 og 1000 opp.

Den er laget i javascript, og jeg er ganske ny i det, så hvis det er noe javascript-guruer her som har tips til å forbedre koden tar jeg gladelig imot tips

[Vaktmester]

Ser ut som et fint lite prosjekt for å lære litt enkel koding. :-) Men det er vel et godt stykke unna å være den beste algoritmen for å finne primtall du bruker der... Hvis du vil finne primtall uten at nettleseren henger seg, så vil jeg anbefale å ta en titt på Miller–Rabin testen. http://en.wikipedia.org/wiki/Miller%E2% ... ality_test

[Aleks855]

Du kunne kanskje utfylt litt om hvorfor 1 ikke er et primtall. Å si at "primtall er tall som er større enn 1..." er i og for seg riktig, men det er ikke definisjonen, bare et resultat.

Når det gjelder programmeringa, så ser jeg at du har hardkoda behandlinga av hvor mange faktorer et komposittall har. Dette kunne vært løst bedre ved å bruke ei for-løkke som gjennomløper tabellen med faktorene. På den måten slipper du dette: http://i.imgur.com/SQvwOKV.png

Jeg ser du ikke har noen for-løkker i koden, så jeg vet ikke om du vet hvordan de brukes?

[Raincloud]

Takk for tilbakemeldinger! Miller–Rabin så interessant ut, skal se nærmere på det

Har vært inne på for-løkker, og jeg er enig i at jeg gjorde denne sekvensen ganske så tungvundt Men da jeg prøvde det, ble resultat slik, f.eks. ved tallet 10:
"10 er satt sammen av 2 * 5 *"
i stedet for slik:
"10 er satt sammen av 2 * 5."

Altså, når jeg har nådd enden arrayet, så skal jeg ikke ha en " * " men en ".". Vet det skal gå an, hvis jeg bruker noe ala

Code: Select all

for (var i = 0; i < array.length; i++){

   if (array[i] == array.length){
      msg = msg + ".";
      }
   else{
      msg = msg + " * ";
      }

Men fikk det ikke helt til... Skal se om jeg får det til nå!

[Vaktmester]

Dette er vel knapt pensum i grunnskolematematikk, som er forumet vi er i - men alle arrayer i javascript har en metode som heter join. Derfor kan du skrive koden din (med dine egne variabelnavn, selvsagt, slik:

Code: Select all

var faktorer = [1,2,3,4,5];
var output = faktorer.join(" * ") + ".",

Da har variabelen output verdien

Code: Select all

1 * 2 * 3 * 4 * 5.

[Raincluod]

Aha, det visste jeg ikke om! Tusen takk, fikk det til nå

[Nebuchadnezzar]

Kjempekult at du har laget en primtallkalkulator!
Som de ovenfor sier så finnes det masse smarte metoder for å bestemme om et tall
er primtall elle ei. Grunnen til at dette er interessant er at alle banker bruker store primtall
for å hemmligjøre transaksjonene banken gjør.

For å bestemme om ett tall er primtall eller ei, liker jeg veldig godt
Solovay-Strassen testen

http://planetmath.org/SolovayStrassenTest

Det behagelige er at en ikke må forstå all matematikken bak det.
Tanken er at å primtallsfaktorisere et tall tar lang tid. Så derfor
lar vi primtallet gå igjennom en algoritme eller sekvens.

Dersom algoritmen gir ut 1 er vi 100% sikker på at tallet ikke er primtall.
Dersom algoritmen gir ut 0 er sjangsen maksimalt 50% for at tallet ikke er primtall.

Består primtallet testen to ganger, er sjangsen maksimalt 25% for at tallet ikke er primtall.
Slik fortsetter det, lar vi primtallet gå igjennom testen 14 ganger er det 0.001% sannsynlighet for at
tallet ikke er primtall. Eller med andre ord 99% sikkert at tallet er primtall.

En mindre optimal kode jeg skrev for herrens år siden ser slik ut. Syntaxen er maple
så kan du titte litt på den, prøve å se hva som foregår, og kanskje implementere noe liknende
i java. Spytter koden ut $0$ så er vi sikker på at tallet er sammensatt / ikke primsk. Spytter
den ut $1$ er vi ikke sikker enda.

Code: Select all

% Her er n primtallet vi tester, og k er antall tester primtallet går igjennom.
% Sannsynligheten for at n er primtall dersom n består k tester er 
% P = 1 - 1/2^k 
function [ Y ] = solovay( n,k )
if mod(n,2)~=0
   p = (n-1)/2;
    for i = 1:k
        a = randi(n-1);
        if gcd(a,n)~=1
           Y = 0;
           return
        end
        
        jacobi = jacobi(a,n);
        mod = powermod(a, p, n);

        if jacobi<0
            jacobi = jacobi + n;
        end

        if mod ~= jacobi
           Y = 0; 
           return
        end
    end
Y = 1;
else
Y = 0;    
end

[Raincloud]

Takk for input! Da skal jeg etter hvert prøve å lage en bedre algoritme for å finne primtall. Etter det jeg har skjønt har vi altså:

- Miller–Rabin primality test
- Solovay-Strassen test
- Fermat primality test (fant denne på wiki, men er ikke så mye brukt etter det jeg forstod.)

Først må jeg forstå helt hvordan de fungerer, og deretter prøve å skrive dem i javascript

[Vaktmester]

Her er en forklaring av hvordan man kan implementere Miller-Rabin fra Udacity: http://www.youtube.com/watch?v=p5S0C8oKpsM

Det er gøy og lærerikt å prøve å implementere den selv, men hvis du står fast, så kan du godt implementere den på nettsiden din allikevel: http://rosettacode.org/wiki/Miller-Rabi ... JavaScript

Lykke til :-)