-
Finding nth prime.
Code:
'This code was written by Mert Ener
Private Declare Function GetTime Lib "winmm.dll" Alias "timeGetTime" () As Long
Private mStartTime As Object
Private Sub Button1_Click(sender As Object, e As EventArgs) Handles Button1.Click
mStartTime = GetTime
Dim l, n As Long : Dim m As Long = 1 : Dim p As New List(Of Long)(New Long() {2})
For n = 0 To (Me.TextBox1.Text) - 2 'The textbox you entered for the nth prime.
m = m + 2
For l = 1 To n
If m Mod p(l) = 0 Then
m += 2
l = 0
End If
Next
p.Add(m)
Next
Me.TextBox2.Text = p(n) 'The textbox you get the result.
MsgBox("It took me " & GetTime - mStartTime & " milliseconds to find your prime number.")
End Sub
-
Re: Finding nth prime.
A modified and faster version of the previous code:
Code:
Option Explicit On
Option Infer On
Public Class Form1
Private Declare Function GetTime Lib "winmm.dll" Alias "timeGetTime" () As ULong
Private mStartTime As ULong
'This code was written by Mert Ener
Private Sub Button1_Click(sender As Object, e As EventArgs) Handles Button1.Click
Me.TextBox2.Text = ""
Refresh()
Dim l As ULong = 0 : Dim n As ULong : Dim m As ULong = 1 : Dim p As New List(Of ULong)(New ULong() {2})
mStartTime = GetTime
Select Case CULng(Me.TextBox1.Text)
Case 0
Exit Sub
Case 1
Me.TextBox2.Text = p(0).ToString
GoTo Message
End Select
For n = 0 To CULng(NumericTextBox1.Text) - 2
m = m + 2
Do While p(l) * p(l) <= m
If m Mod p(l) = 0 Then
m = m + 2
l = 1
Else
l += 1
End If
Loop
l = 1
p.Add(m)
Next
Me.TextBox2.Text = p(n).ToString
Message:
MsgBox("It took me " & GetTime - mStartTime & " milliseconds to find your prime number.")End Sub
-
Re: Finding nth prime.
if anyone needs prime numbers.. I calculated them all up to 100,000,000... it took close to a year on a P4 3.2ghz and I was finding about 100 per second... I divided it up into files of intervals of 1 million, then in folders for the billions, and zipped it... I think it's about 10 GB
I found there was still about 4% prime numbers at 100 billion, which really surprised me
*Edit... the 100,000,000 above should have another 3 zeros, making it 100 billion
-
Re: Finding nth prime.
I think it is not absolutely true to say "There are 4% of prime numbers in 100.000.000.000". They are virtually infinite so you can't give a percentage.
This code calculates the 100.000.000th prime in less than half an hour with an E8400. There are much faster codes using multithreaded "Sieve of Eratosthenes" which are 10 times faster than mine. But this code is very simple and direct.
-
Re: Finding nth prime.
It's perfectly fair to say there are 4% primes around 100 billion... I tested every number from 100 billion to 100,001,000,000, and found about 40,000 prime numbers, which is 4%.. I am not saying that 4% of ALL numbers are prime... currently the largest known prime number is 2^57,885,161 − 1... which has 17.4 million digits... that's a little out of my league, and I don't know what percentage are prime way up there...
I noticed I mistyped in my previous post, I meant to say 100 billion, not 100,000,000 like I had typed, sorry about that... 100 million happens pretty fast on my computer as well.
In my code it would only check against prime numbers... my code looked something like...
Code:
private function IsItPrime(testnumber as ulong) as boolean
dim PrimeArray() as ulong 'array of prime numbers, including 2 as the first prime
dim TestNumber as ulong 'The number we're testing to be prime
dim TestLimit as ulong = sqrt(testnumber)
dim i as integer = 0
do
dim q as ulong = primearray(i) 'gets the prime number stored in the array
i += 1 'increment the index
if testnumber mod q =0 then return false 'if it's not prime, exit
loop until q > Testlimit
return true
end function
that's the nitty gritty of my code
-
Re: Finding nth prime.
Ahhh, sorry, my mistake. You said 4% of 100 billion are primes. English is not my mother tounge so sometimes I got things wrong.
I understood something like "100 billion contains 4% of primes"... That's why I said " They are virtually infinite so you can't give a percentage." But now I got what you mean ;)
Yeah, I couldn't test 100 billion because type Integer allows 2.147.483.647 max. I would like to test it someday :)
-
Re: Finding nth prime.
I think I used Ulongs
Another great exercise is to make a calculator that does long division, multiplication, addition and subtraction (like you learned in elementary school)... I made one in VB6 which I haven't been able to do in .net because VB6 allows negative array indexes, which I used for the decimal... I tested it to multiply 2 64,000 digit numbers together.. I think I still have the code somewhere too
-
Re: Finding nth prime.
