Kirjautuminen

Haku

Tehtävät

Koodit: VB.NET: Onko alkuluku

Kirjoittaja: tnb

Kirjoitettu: 27.01.2004 – 27.01.2004

Tagit: vinkki

Onko joku luku alkuluku vai ei, voidaan selvittää helposti jakamalla kaikilla lukua pienemmillä luvuilla. Jos jokin jakojäännös on nolla niin ei ole alkuluku. Testi tarvitsee toistaa vain luvuille 2... neliöjuuri ko. luvusta.

Todella suurilla luvuilla tämä testaus tapa hyytyy mahdottomuuteensa. Avuksi tulee Fermat'n pieni teoreema:

jos k^(A-1) mod A ei ole 1 niin A ei ole alkuluku

Toistamalla testi riittävän usealla k:n arvolla saadaan riittävällä todennäköisyydellä tietää onko suuri luku alkuluku (=todennäköinen alkuluku).

Oheinen ohjelma demoaa testiä. k:n arvot on otettu 100sta ensimmäisestä alkuluvusta. Suurin kelpaava luku on 281474976710676 ja siitä alaspäin. Vauhtia tulee 4000 ... 5000 lukua sekunnissa (ADM 1.66 GHz).

Tee: textbox1,2,3 ja buttonit 1 ja 2

Itse algoritmi

Private Function TestIfPrime(ByVal A As Long) As Boolean
       'Fermat's little theorem
       ' if k^(A-1) mod A is not 1 then A is not a prime
       Dim i As Integer
       'check small primes
       If ((A Mod 2) = 0) And A <> 2 Then
           TestIfPrime = False
           Exit Function
       End If
       For i = 3 To 13 Step 2
           If ((A Mod i) = 0) And A <> i Then
               TestIfPrime = False
               Exit Function
           End If
       Next i

       'first 100 prime numbers as k's
       Dim pri() As Long = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541}
       Dim P As Long

       Dim c As Integer = UBound(pri)
       P = A - 1
       For i = 1 To c
           If A = pri(i) Then
               TestIfPrime = True
               Exit Function
           End If
           If Power_mod_N(pri(i), P, A) <> 1 Then
               TestIfPrime = False
               Exit Function
           End If
       Next i
       TestIfPrime = True
   End Function

Ohjelma potenssin jäköjäännöksen laskuun

Private Function Power_mod_N(ByVal P As Long, ByVal d As Long, ByVal n As Long) As Long
        'A = (P ^ D) Mod N , P must be less than N
        'A = (P^e2 * P^e2 * P^e3) Mod N where D= 2*e2+e3 , e3 is 1 or 0
        'A = ((P^e2)mod N) * ((P^e2)mod N)) * ((P^e3)mod N))Mod N
        'then recursive call untill exponent is one
        ' because P<N then P^1 mod N = P
        Dim e2 As Long
        Dim e3 As Long
        Dim a2 As Long
        Dim a3 As Long
        Dim a4 As Decimal
        Dim a5 As Decimal
        Dim a6 As Decimal

        e2 = d \ 2
        e3 = d - 2 * e2

        If e2 = 1 Then 'recursion ends
            a2 = P
        Else
            a2 = Power_mod_N(P, e2, n)  'recursion continues
        End If

        If e3 = 1 Then
            a3 = P 'a3=P when e3=1
        Else
            a3 = 1 ' P^0
        End If

        'A= (a2*a2*a3) mod N
        'A=((a2*a2)mod n * a3 )mod n
        a6 = CDec(a2) ' convert to decimal
        a4 = a6 * a6
        a5 = a4 Mod CDec(n)
        a4 = a5 * CDec(a3)
        Power_mod_N = CLng(a4 Mod CDec(n))
    End Function

Testinapit

Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
        'pienimmästä ylöspäin
        Dim i As Long
        Dim count As Long = 1
        Dim ts As TimeSpan
        Dim t1 As Date
        Dim t2 As Date
        TextBox1.Text = "Alhaalta ylös 100 000 lukua"
        TextBox3.Text = ""
        t2 = Now
        For i = 3 To 100000 Step 2
            If TestIfPrime(i) Then
                count = count + 1
                TextBox2.Text = CStr(count)
                Application.DoEvents()
            End If
        Next i
        t1 = Now
        ts = t1.Subtract(t2)
        TextBox3.Text = CStr(Int(i / ts.TotalSeconds)) + " lukua sekunnissa"

    End Sub

    Private Sub Button2_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button2.Click
        'suurimmasta alaspäin testi
        Dim i As Long
        Dim count As Long = 1
        Dim ts As TimeSpan
        Dim t1 As Date
        Dim t2 As Date
        Dim m As Long

        TextBox1.Text = "Ylhäältä alas 100 000 lukua"
        TextBox3.Text = ""
        t2 = Now
        For i = 2 To 100000 Step 2
            m = 281474976710677 - CLng(i) 'suurimmasta alaspäin
            If TestIfPrime(m) Then
                count = count + 1
                TextBox2.Text = CStr(count)
            End If
            Application.DoEvents()
        Next i
        t1 = Now
        ts = t1.Subtract(t2)
        TextBox3.Text = CStr(Int(i / ts.TotalSeconds)) + " lukua sekunnissa"
    End Sub

Kommentit

sooda [29.01.2004 10:16:57]

#

"ADM 1.66 GHz" :D mulla on ainaki amd... :D

Gwaur [29.01.2004 15:39:06]

#

Mikähän toi soodan "kommentin" pointti? :P

Heikki [30.01.2004 16:01:51]

#

Tuossa on listattuja alkulukuja, mutta luku 0 ei ole alkuluku...

NanoSoft [23.02.2006 21:18:03]

#

johan on tehty vaikeasti

ErroR++ [30.03.2011 16:49:39]

#

Toimihan se, mutta en älyä mitän.

ErroR++ [30.03.2011 16:50:24]

#

Tarkoitan miten.

Jaska [28.01.2021 22:57:22]

#

"jos k^(A-1) mod A ei ole 1 niin A ei ole alkuluku"

Tämä on väärin. Esimerkiksi 2^(2-1) = 0 mod 2 vaikka 2 on alkuluku. Pitäisi olla muodossa "Jos k^(A-1) mod A ei ole 1 ja k ei ole jaollinen A:lla, niin A ei ole alkuluku."

PekkaJari [07.05.2021 13:13:24]

#

Ei kaksi voi olla alkuluku, koska sen voi jakaa 2:lla jolloin saa arvon 1 (1, 3 .. jne ovat)

Teuro [07.05.2021 13:21:46]

#

PekkaJari kirjoitti:

Ei kaksi voi olla alkuluku, koska sen voi jakaa 2:lla jolloin saa arvon 1 (1, 3 .. jne ovat)

Alkuluvun määritelmän mukaan luku saa olla jaollinen vain itsellään ja luvulla 1. Luku 2 täyttää molemmat ehdot hyvin. Tämän määritelmän mukaan luku 2 on kyllä alkuluku.

Kirjoita kommentti

Muista lukea kirjoitusohjeet.
Tietoa sivustosta