83 lines
2 KiB
Text
83 lines
2 KiB
Text
' version 10-12-2016
|
|
' compile with: fbc -s console
|
|
|
|
Dim Shared As Byte isPrime()
|
|
|
|
Sub sieve(m As UInteger)
|
|
|
|
Dim As Integer i, j
|
|
ReDim isPrime(m)
|
|
|
|
For i = 4 To m Step 2
|
|
isPrime(i) = 1
|
|
Next
|
|
|
|
For i = 3 To Sqr(m) Step 2
|
|
If isPrime(i) = 0 Then
|
|
For j = i * i To m Step i * 2
|
|
isPrime(j) = 1
|
|
Next
|
|
End If
|
|
Next
|
|
|
|
End Sub
|
|
|
|
' ------=< MAIN >=------
|
|
|
|
#Define max 1000000 'upto 2^30 max for 32bit OS
|
|
|
|
Dim As UInteger a(), lt_prime(5000), rt_prime(100)
|
|
Dim As UInteger i, j, j1, p1, p2, left_max, right_max
|
|
|
|
sieve(max)
|
|
|
|
' left truncatable primes
|
|
' if odd and ends with 3 or 7, never ends 1 or 9 (no prime
|
|
' never ends on a 2 or 5 and starts with 1 to 9
|
|
lt_prime(1) = 3 : lt_prime(2) = 7
|
|
p1 = 1 : p2 = 2
|
|
|
|
Do
|
|
For i = 1 To 9
|
|
j = Val( Str(i) + Str(lt_prime(p1)) )
|
|
If j > max Then Exit Do
|
|
If isPrime(j) = 0 Then ' if prime then add to the list
|
|
p2 += 1
|
|
lt_prime(p2) = j
|
|
If Left_max < j Then left_max = j
|
|
End If
|
|
Next
|
|
p1 += 1
|
|
Loop Until p1 > p2 ' no more numbers to process
|
|
|
|
' right truncatable prime
|
|
' start with 2, 3, 5 or 7 and end with 1, 3, 7 or 9
|
|
rt_prime(1) = 2 : rt_prime(2) = 3 : rt_prime(3) = 5 : rt_prime(4) = 7
|
|
p1 = 1 : p2 = 4
|
|
Dim As UInteger end_num(1 To 4) => {1, 3, 7, 9}
|
|
|
|
Do
|
|
j1 = rt_prime(p1) * 10
|
|
If j1 > max Then Exit Do
|
|
For i = 1 To 4
|
|
j = j1 + End_num(i)
|
|
If isprime(j) = 0 Then ' if prime then add to the list
|
|
p2 += 1
|
|
rt_prime(p2) = j
|
|
' If right_max < j Then right_max = j
|
|
End If
|
|
Next
|
|
p1 += 1
|
|
Loop Until p1 > p2 ' no more numbers to process
|
|
' the last one added is the biggest
|
|
right_max = rt_prime(p2)
|
|
|
|
Print
|
|
Print "The biggest left truncatable prime below"; max; " is "; left_max
|
|
Print "The biggest right truncatable prime below"; max; " is "; right_max
|
|
|
|
' empty keyboard buffer
|
|
While Inkey <> "" : Wend
|
|
Print : Print "hit any key to end program"
|
|
Sleep
|
|
End
|