grublet over i 9 år

For mere en d 2000 år siden opfandt en metode der hedder The Sieve of Eratosthenes (eller noget i den dur) :-)
Metoden gik ud på at skrive alle tal op og derefter strege dem ud der IKKE var primtal.
Men egntlig eregne regler ved jeg nu ikke.
jeg skal kigge på det, men du får jo nok svar fra en anden :-)

Et lille bidrag, på engelsk: http://www.utm.edu/research/primes/

Her er et lille eksempel :

Private Sub Command1_Click()
Dim PrimNr As Integer
Dim i As Integer
Dim ErPrime As Boolean
ErPrime = True

PrimNr = Val(Text1.Text)
For i = 2 To (PrimNr - 1)
    If PrimNr Mod i = 0 Then
        ErPrime = False
    End If
Next

If ErPrime = True Then
List1.AddItem PrimNr
End If
End Sub

med få tilretninger kan man f.eks. få den til at søge mellem 2 givne tal

hehe mange sjove ting på den side, f.eks. er følgende ord primtal : ( altså i 32-tals systemet )

DANISH
BROOKLYN
CHAMPION
EARTH
KURT

Dejboj hvad er din mail?? eller icq? mit icq nummer er: 83999178
min mail er: Bjorn.B@mail1.stofanet.dk
Vil bare gerne snakke med dig om HH!

erikjakobsen// fedt link - men af en eller anden mærkelig grund mener de ikke at der findes et program der bare kører derudaf ?
Det bedste de havde var et der kunne finde primtal på op til 80 cifre

Primtal i sig selv er uinteressante. De store primtal (de største man kender har en speciel form, og hedder
Mersenne) er lidt sjove, fordi de er de største. Og så de primtal man bruger til moderne kryptering. Men de
bliver ikke fundet ved division. Så der er ingen grund til ligesom at finde \"dem allesammen\". Der er mange,
ja faktisk uendeligt mange.

Interessant emne...
Jeg har selv gjort mig nogle overvejelser omkring det at finde primtal, omend det er et par år siden. Derfor, da jeg så dette spørgsmål, fandt jeg straks et par gamle programmer frem!
Det er rigtigt, at der ikke er nogen decideret formel for at finde primtal, men så må man jo prøve sig frem.
Følgende kode er godt nok i C++ og ikke VB (jeg bryder mig ikke om VB), men det skulle nu være ret let at se sammenhængen (ellers spørg).

while(true)
{
  if(Primtest % D == 0) //Divisor går op i tal => IKKE primtal
  {
    Primtest += 2; //Næste ulige tal til test
    D=3; //Reset divisor
  }
  else
  if(D*D >= Primtest) //Det er kun nødvendigt at teste op til kvadratroden af divisor
  {
    cout << Primtest << \" \" << flush; //Det er et primtal, udskriv!
    D=3; //Reset divisor
    Primtest += 2; //Næste ulige tal til test
  }
  else
    D += 2; //Inkrementér divisor
};
cout << \"\\n\\n\";
    return 0;

Som i kan se er det altså ret let at lave et program der bare \"kører\" derudaf! Problemet her er bare datatypen. En almindelig heltalsvariabel er typisk 16- eller 32bit, altså kun nok til enten 65536 eller 4294967296 som maksimale tal!!!

Java indeholder dog en klasse til meget store tal, så det var jo en mulighed...

Den algoritme jeg viser her finder primtal fra og med 5 og opefter.
Grunden til at den ikke tager 2 og 3 med, skyldes at jeg har forsøgt at optimere den så meget som muligt!

Vi er sikkert enige om, at et tal er et primtal hvis kun 1 og tallet selv går op i det. Altså er det klart at alle lige tal (pånær 2) ikke er primtal, og derfor heller ikke behøver testes. Herved fås en hastighedsforøgelse på en faktor 2, dog med den lille omkostning at det første primtal i rækken, nemlig 2, ikke findes af algoritmen!

Når man så tester på om der er nogle tal der går op i det tal man undersøger, vil man normal teste op til hvad? I Brians eksempel tidligere bruger han tallet selv minus 1. En bedre løsning ville vel være til halvdelen af tallet. Tag fx tallet 11, når dets halve værdi passeres (6), må det være klart, at ingen højere tal går op heri.
Graver man lidt dybere viser det sig endda at det kun er nødvendigt at fortsætte til kvadratroden af tallet. Dette skyldes, at tallene kan primfaktoreres, hvorfor der findes et matematisk bevis. Derfor testen \"if(D*D >= Primtest)\" i koden.
Herved mister vi dog muligheden for at finde tallet 3, som primtal...

Man kan desuden starte med 3, som divisor, da 1 jo altid går op og 2 er et lige tal (som nævnt er primtal ulige tal,  og lige tal går derfor ikke op i dem)

Hvis nogle er interesseret, har jeg lavet et lille Windows-program, der udnytter en lettere modificeret version af ovenstående algoritme til at finde primtal og skrive dem til en tekstfil. Send da blot en e-mail til mig på adressen: jacpost@post.tele.dk, så skal jeg sende en kopi af programmet (det fylder 132KB).

Jacob

Hey jpk - jeg har prøvet at maile til dig på den adresse du har sendt - men jeg fik en failure notice - den kunne ikke finde din adresse - det ser ellers rigtigt spændende ud det du har sendt - Jeg vil meget gerne have en kopi af programmet på denboj@worldonline.dk

Der er ikke noget at sige til, at du fik din mail tilbage! jeg har nemlig skrevet forkert, undskyld!
Min adresse er: jacpost@post6.tele.dk
Jeg skal straks sende dig en kopi af programmet...

jpk - helt suverent lille program jeg fik fra dig der - jeg har prøvet med et par forskellige max tal og jeg synes at det virker til at programmet går ned hvis man vælger et for stort tal - hvor stor er begrænsningen ?
det lykkedes mig dog at finde op til 3605233 - der blev lige lavet et .txt dokument på 1.82 MB

erikjacobsen// jeg synes netop at det interessante er at der er en uendeligheds faktor - Jeg kunne også se at der var sat navn på hvem der havde fundet det største primtal i de links du gav mig - så jeg synes da at det virker som om der er nogen der mener at der er prestige forbundet med at kunne finde et primtal så højt som muligt.

Faktisk kan det sammenlignes lidt med Pi - der er jo også et uendeligt antal decimaler på.

Begrænsningen for programmet er 32bit, altså godt 4 mia. prøv at højreklikke på ikonet og vælg \"Om WinPrim\", der står det præcise tal.

Grunden til at du tror programmet er gået ned, skyldes at beregningen foregår i dets primære tråd. Eftersom den har travlt med at regne, kan operativsystemet ikke komme i kontakt med programmet...
-Man burde nok lave beregningen i en sekundær tråd!

Prøv bare at indtaste henholdsvis tallene 4000000000 og 4000001000, altså et interval på 1000. Så vil du se at programmet ikke er gået ned, men finder primtallene imellem!

jpk: ved godt jeg er 5 år bagud, men hvis du stadig ligger inde med det, må du da gerne sende det til mig på " gertsen snabela gmail dot com " (oversæt snabela til @ og dot til . naturligvis :-) - hader spam crawlers)