Project Euler Problem 7

[Michael Clease]

Here is my first attempt watch out its very slow.



' By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
' What is the 10001st prime number?

uses "Console"

DIM n, m AS LONG
DIM Counter AS LONG
DIM Primes AS DWORD
DIM sMsg AS STRING

'...
Dim T1, T2 As QUAD
'---Initialize hi resolution timer
HiResTimer_Init

printL ("This will take some time about 10 minutes or more")

T1 = hirestimer_get

n = 1
do
incr n ' start at 2
counter = 2 ' we know that 1 and the number its self works so we start at 2
FOR m = 2 to n/2 ' to save time we only do half the numbers and check
IF MOD( n,m) = 0 THEN INCR Counter
NEXT
IF counter <=2 THEN INCR Primes 'sMsg += VAL(n) + " " : Primes += 1
loop until Primes >= 10001

T2 = hirestimer_get

printL ("Answer: " + STR$(n))
PRINTL ("Elapsed time in seconds: " & FORMAT$((T2-T1)/1000000)
CONSOLE_WAITKEY

[ErosOlmi]

Too slow :unguee: :grrrr:

I've developed a IsPrime(Number) function that returns if a number is a prime number.
It will be present in next thinBasic release.

With this function, finding the 10001st prime number takes 0.7 secs on my computer.
I know, it is a trick but ... thinBasic is full of tricks.

Ciao
Eros

[ErosOlmi]

An updated version that takes less time using a function I've found here: http://www.devx.com/vb2themax/Tip/19051



' By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
' What is the 10001st prime number?

uses "Console"

DIM n, m AS LONG
DIM Counter AS LONG
DIM Primes AS DWORD
DIM sMsg AS STRING

'...
Dim T1, T2 As QUAD
'---Initialize hi resolution timer
HiResTimer_Init

printL ("Calculating the 10001st prime number")

T1 = hirestimer_get

n = 1
do
incr n ' start at 2
IF Local_IsPrime(n) THEN
INCR Primes
printat primes, 10, 10
end if

loop until Primes >= 10001

T2 = hirestimer_get

printL ("Answer: " + STR$(n))
PRINTL ("Elapsed time in seconds: " & FORMAT$((T2-T1)/1000000) )
CONSOLE_WAITKEY


Function Local_IsPrime(ByVal lnumber As Long) As Boolean
' manually test 2 and 3
If lnumber > 3 Then
If mod(lnumber, 2) = 0 Then Exit Function
If mod(lnumber, 3) = 0 Then Exit Function
End If
' we can now avoid to consider multiples
' of 2 and 3. This can be done really simply
' by starting at 5 and incrementing by 2 and 4
' alternatively, that is:
' 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, ...
Dim divisor As Long
Dim increment As Long
Dim maxDivisor As Long

divisor = 5
increment = 2
' we don't need to go higher than the square
' root of the number
maxDivisor = Sqr(lnumber) + 1

Do Until divisor > maxDivisor
If mod(lnumber, divisor) = 0 Then Exit Function
divisor = divisor + increment
' this modifies 2 into 4 and viceversa
increment = 6 - increment
Loop

' if we get here, the number is prime
function = %True

End Function

[Michael Clease]

That script crashes my TB is has something to do with the Local_ISPrime, if I rename it, itdoesnt crash with an error 18.

[Petr Schreiber]

Hi Michael,

I think that isprime just before T2 = ... shouldn't be there.
Then it works and it is quite fast!

[ErosOlmi]

oops, sorry. Now fixed.
I left an incorrect line by mistake.

[Michael Clease]

Anyway I think is dividing is the wrong way to go better to multiply :eusadance:

Just need an array command to fill the array for me (faster) :escribe:



' By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
' What is the 10001st prime number?

uses "Console"

%Count = 105000

DIM n, m AS DWORD
DIM Counter AS DWORD
DIM Primes AS DWORD
DIm Numbers(%Count) AS DWORD
DIM aPrimes(%Count) AS DWORD
DIm num AS DWORD
DIM sMsg AS STRING
'...
Dim T1, T2 As QUAD
'---Initialize hi resolution timer
HiResTimer_Init


T1 = hirestimer_get
For n = 2 to %Count
numbers(n) = n ' Build table
NEXT
FOR num = 2 TO %Count
For n = 2 to %Count
IF num*n >= %Count THEN EXIT FOR ' Filter any multiples
Numbers(num*n) = 0
NEXT
NEXT
'Counter = 1
do
FOR N = 2 TO UBOUND(Numbers)
IF Numbers(n) <> 0 THEN INCR Counter : aPrimes(Counter) = n
NEXT
LOOP Until Counter >= 10001
T2 = hirestimer_get
'FOR n = 1 to 10
'sMsg += VAL(Numbers(n))+" " + VAL(aPrimes(n))+" " +$CRLF
'NEXT
'MSGBOX 0, sMSG 'VAL(aPrimes(1))+" " 'smsg

printL ("Answer: " + VAL(aPrimes(10001)))
PRINTL ("Elapsed time in seconds: " & FORMAT$((T2-T1)/1000000))
CONSOLE_WAITKEY