Sub Process_Globals
Private numbers(10000000) As Boolean
Private primes As List
End Sub
Sub AppStart (Args() As String)
Dim n As Long = DateTime.Now
primes.Initialize
For i = 2 To numbers.Length - 1
If numbers(i) = False Then
primes.Add(i)
For i2 = 2 * i To numbers.Length - 1 Step i
numbers(i2) = True
Next
End If
Next
Log($"took: ${DateTime.Now - n} ms"$)
Log("number of primes: " & primes.Size)
Log("last 20 primes")
For i = primes.Size - 21 To primes.Size - 1
Log(primes.Get(i))
Next
End Sub
Takes 118 milliseconds to find all primes smaller than 10,000,000.
Takes 42 seconds to find all primes smaller than 1,000,000,000.
With @Erel's method.
Takes 241 ms to find all primes smaller than 10,000,000.
With my method (Sieve of Eratosthenes)
Takes 85 ms to find all primes smaller than 10,000,000.
however it throws an OutOfMemory: Java heap space error when I try with 1,000,000,000
B4X:
Sub Process_Globals
Private range As Int = 10000000
Private numbers(range) As Boolean
Private primes As List
Private primeN As Int
Private primeI As Int
Private primeFlag As Boolean
Private is_prime(range) As Boolean
End Sub
Sub AppStart (Form1 As Form, Args() As String)
Dim n As Long = DateTime.Now
primes.Initialize
For primeN = 3 To numbers.Length - 1 Step 2
is_prime(primeN) = True
Next
Private max_i As Int = Sqrt(range) +1
For i = 3 To max_i
If is_prime(i) Then
Private max_j As Int = range / i
If (max_j Mod 2 = 0) Then max_j = max_j - 1
For j = max_j To i Step -2
If (is_prime(j)) Then
is_prime(i * j) = False
End If
Next
End If
Next
For i = 3 To range Step 2
If (is_prime(i)) Then
primes.Add(i)
End If
Next
' Dim n As Long = DateTime.Now
' primes.Initialize
' For i = 2 To numbers.Length - 1
' If numbers(i) = False Then
' primes.Add(i)
' For i2 = 2 * i To numbers.Length - 1 Step i
' numbers(i2) = True
' Next
' End If
' Next
Log($"took: ${DateTime.Now - n} ms"$)
Log("number of primes: " & primes.Size)
Log("last 20 primes")
For i = primes.Size - 21 To primes.Size - 1
Log(primes.Get(i))
Next
End Sub