My vbScript answer to the Google Question. {the first 10 digit prime in e}.com

Rember the google question {the first 10 digit prime in e}.com ?

Here is my vbscript answer which finds the first 10 digit prime in e
in half a second or so (depending upon your hardware).
Note, this code is built for speed rather than readability (or 'write
only code' as we call it here!).



s=Timer()
Dim a(100000)
r=Round(Sqr(100000))
For p=2 To r
While a(p)=True
p=p + 1
Wend
x=p * 2
While x<=100000
a(x)=True
x=x+p
Wend
Next
e="2718281828459045235360287471352662497757247093699959574966967627724076630353547594571382178525166427427466391932003059921817413596629043572900334295260595630738132328627943490763233829880753195251019011573834187930702154089149934884167509244761460668082264800168477411853742345442437107539077744992069551702761838606261331384583000752044933826560297606737113200709328709127443747047230696977209310141692836819025515108657463772111252389784425056953696770785449969967946864454905987931636889230098793"
For p=1 To Len(e)-9
c=Mid(e,p,10)
b=True
For x=2 To 100000
If a(x)=False Then
r=CDbl(c)/CDbl(x)
If r=Round(r) Then
b=False
Exit For
End If
End If
Next
If b=True Then
MsgBox c & " is the first 10 digit prime in e at p:" & p & vbCrLf &
"done in : " & Timer() - s & " seconds"
WScript.Quit
End If
Next

Richard
Thu Sep 06 10:32:38 PDT 2007

Several things can be done to improve this algorithm, but the single biggest
speed improvement is to use Option Explicit and delare all variables in Dim
statements. My quick tests show an improvement from 0.58 sec to 0.36 sec. If
you use long descriptive variable names, add comments and white space, and
indent loops and If/Then blocks, the code will be easy to read,
troubleshoot, and modify, but just as fast. I often find that the more
"compact" code is, the slower and more error prone it is, besides being
harder to understand.

--
Richard Mueller
Microsoft MVP Scripting and ADSI
Hilltop Lab - http://www.rlmueller.net
--

"Tim" <TimJordanVBS@hotmail.com> wrote in message
news:1189094458.978575.58390@o80g2000hse.googlegroups.com...
> Rember the google question {the first 10 digit prime in e}.com ?
>
> Here is my vbscript answer which finds the first 10 digit prime in e
> in half a second or so (depending upon your hardware).
> Note, this code is built for speed rather than readability (or 'write
> only code' as we call it here!).
>
>
>
> s=Timer()
> Dim a(100000)
> r=Round(Sqr(100000))
> For p=2 To r
> While a(p)=True
> p=p + 1
> Wend
> x=p * 2
> While x<=100000
> a(x)=True
> x=x+p
> Wend
> Next
> e="2718281828459045235360287471352662497757247093699959574966967627724076630353547594571382178525166427427466391932003059921817413596629043572900334295260595630738132328627943490763233829880753195251019011573834187930702154089149934884167509244761460668082264800168477411853742345442437107539077744992069551702761838606261331384583000752044933826560297606737113200709328709127443747047230696977209310141692836819025515108657463772111252389784425056953696770785449969967946864454905987931636889230098793"
> For p=1 To Len(e)-9
> c=Mid(e,p,10)
> b=True
> For x=2 To 100000
> If a(x)=False Then
> r=CDbl(c)/CDbl(x)
> If r=Round(r) Then
> b=False
> Exit For
> End If
> End If
> Next
> If b=True Then
> MsgBox c & " is the first 10 digit prime in e at p:" & p & vbCrLf &
> "done in : " & Timer() - s & " seconds"
> WScript.Quit
> End If
> Next
>

Richard
Thu Sep 06 12:32:34 PDT 2007

A version that tries all odd numbers as possible factors and takes about
0.14 seconds (compared to the 0.36 and 0.58 seconds I reported earlier).
Watch line wrapping:
===========
Option Explicit

Dim lngStart, k, dblCandidate, dblFactor, dblLimit
Dim dblTemp, blnPrime, lngEnd

Const E =
"2718281828459045235360287471352662497757247093699959574966967627724076630353547594571382178525166427427466391932003059921817413596629043572900334295260595630738132328627943490763233829880753195251019011573834187930702154089149934884167509244761460668082264800168477411853742345442437107539077744992069551702761838606261331384583000752044933826560297606737113200709328709127443747047230696977209310141692836819025515108657463772111252389784425056953696770785449969967946864454905987931636889230098793"

lngStart=Timer()

For k = 1 To Len(E) - 9
dblCandidate = CDbl(Mid(E, k, 10))
dblLimit = Fix(Sqr(dblCandidate))

blnPrime = True
dblFactor = 2
Do Until (dblFactor > dblLimit)
dblTemp = dblCandidate / dblFactor
If (dblTemp = Fix(dblTemp)) Then
' Factor found
blnPrime = False
Exit Do
End If
If (dblFactor = 2) Then
dblFactor = 3
Else
dblFactor = Round(dblFactor + 2)
End If
Loop

If (blnPrime = True) Then
Wscript.Echo dblCandidate
lngEnd = Timer()
Wscript.Echo "Time required: " & CStr(lngEnd - lngStart)
Wscript.Quit
End If
Next
Wscript.Echo "No primes found"
lngEnd = Timer()
Wscript.Echo "Time required: " & CStr(lngEnd - lngStart)
===========
I've used algorithms in the past that try all candidate factors that are not
multiples of 2, 3, or 5 (after the first few). For example, the possible
factors to try would be:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, ...

The first prime candidate factor tried (unnecessarily) is 49. In other
languages where this sequence can be more efficiently generated, this makes
the algorithm faster. In VBScript, when dealing with such small numbers (10
digits), it slows down the program.

I don't like using double data types in cases like this, because of the
possible round off errors. Unfortunately Longs overflow here. In this case
the answer seems correct.

--
Richard Mueller
Microsoft MVP Scripting and ADSI
Hilltop Lab - http://www.rlmueller.net
--

Richard
Thu Sep 06 12:47:18 PDT 2007

I found a better way to generate the sequence I was talking about. This
version takes about 0.11 seconds (instead of 0.14 in the previous example).
For each 10 digit number, the program checks if the number is prime by
trying all possible factors in the sequence:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 49, 53, ...

up to the square root of the number. It avoids all divisors after the first
few that are multiples of 2, 3, or 5.
================
Option Explicit

Dim lngStart, k, dblCandidate, dblFactor, dblLimit, dblTemp, blnPrime
Dim lngEnd, arrIncr, j

Const E =
"2718281828459045235360287471352662497757247093699959574966967627724076630353547594571382178525166427427466391932003059921817413596629043572900334295260595630738132328627943490763233829880753195251019011573834187930702154089149934884167509244761460668082264800168477411853742345442437107539077744992069551702761838606261331384583000752044933826560297606737113200709328709127443747047230696977209310141692836819025515108657463772111252389784425056953696770785449969967946864454905987931636889230098793"

lngStart=Timer()

' Sequence to increment divisors.
' The sequence 4, 2, 4, 2, 4, 6, 2, 6 is repeated.
arrIncr = Array(1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6)

For k = 1 To Len(E) - 9
dblCandidate = CDbl(Mid(E, k, 10))
dblLimit = Fix(Sqr(dblCandidate))

blnPrime = True
dblFactor = 2
j = 0
Do Until (dblFactor > dblLimit)
dblTemp = dblCandidate / dblFactor
If (dblTemp = Fix(dblTemp)) Then
' Factor found
blnPrime = False
Exit Do
End If
dblFactor = Round(dblFactor + arrIncr(j))
j = j + 1
If (j > 10) Then
j = 3
End If
Loop

If (blnPrime = True) Then
Wscript.Echo dblCandidate
lngEnd = Timer()
Wscript.Echo "Time required: " & CStr(lngEnd - lngStart)
Wscript.Quit
End If
Next
Wscript.Echo "No primes found"
lngEnd = Timer()
Wscript.Echo "Time required: " & CStr(lngEnd - lngStart)

--
Richard Mueller
Microsoft MVP Scripting and ADSI
Hilltop Lab - http://www.rlmueller.net
--

Tim
Fri Sep 07 03:15:08 PDT 2007

Hi Richard,

thanks very much for the feedback. I niavely assumed that the fastest
code would be the smallest. I should have at least tried using Option
Explicit.... O well, I won't forget that tip in a hurry thanks!
That's interesting that using your 'imperfect' sequence of 'probable'
primes is faster than my method of using Eratosthenes sieve to
precalculate the actual primes.
I guess a lot depends upon where in E the first prime is, possibly if
it was very much further down (or if the question was 'find the
millionth 10 digit prime in e'), then my method might catch up (using
Option Explicit of course!).

One annoying thing which means I can't actually run your code, is that
I keep getting a type mismatch error on this line:

dblCandidate = CDbl(Mid(E, k, 10))

Iv'e tried:

strTemp = Mid(E, k, 10)
dblCandidate = CDbl(strTemp)

but I still get the type mismatch.

I have also done
MsgBox strTmp
Just to confirm it really looks like a 10 digit number (and it does).

I've come accross a oddities like this before where vbScript code
that's happy on one machine gives type mismatches on another...

Any clues as to why?

Tim.

Richard
Fri Sep 07 06:07:04 PDT 2007

I checked the code I posted on several computers, with versions of WSH from
5.1 to 5.7. The CDbl function works the same on them all. In your code you
have:

c=Mid(e,p,10)
...
r=CDbl(c)/CDbl(x)

which is exactly the same, the string c (a 10 digit string) is converted to
a double. The only difference is I made E a constant and you assigned the
string to a variable. Maybe try your assignment. Also, you can echo the
datatype of strType with:

MsgBox(TypeName(strTemp))

Also, you can check if it is numeric with:

MsgBox(IsNumeric(strTemp))

0 means false and -1 means true, so you should see -1. Otherwise, I'm
stumped.

I had to check my Knuth book "Seminumerical Algorithms" regarding the
Eratosthenes sieve. The text says you should be able to generate the array
with no multiplication. The implication is that longer code that avoids
multiplication will be more efficient. I'm sure there's a trade off. Also,
10 digit numbers are not very big. The sieve may not be faster until you are
dealing with much larger numbers.

--
Richard Mueller
Microsoft MVP Scripting and ADSI
Hilltop Lab - http://www.rlmueller.net
--

"Tim" <TimJordanVBS@hotmail.com> wrote in message
news:1189160108.639652.318380@o80g2000hse.googlegroups.com...
> Hi Richard,
>
> thanks very much for the feedback. I niavely assumed that the fastest
> code would be the smallest. I should have at least tried using Option
> Explicit.... O well, I won't forget that tip in a hurry thanks!
> That's interesting that using your 'imperfect' sequence of 'probable'
> primes is faster than my method of using Eratosthenes sieve to
> precalculate the actual primes.
> I guess a lot depends upon where in E the first prime is, possibly if
> it was very much further down (or if the question was 'find the
> millionth 10 digit prime in e'), then my method might catch up (using
> Option Explicit of course!).
>
> One annoying thing which means I can't actually run your code, is that
> I keep getting a type mismatch error on this line:
>
> dblCandidate = CDbl(Mid(E, k, 10))
>
> Iv'e tried:
>
> strTemp = Mid(E, k, 10)
> dblCandidate = CDbl(strTemp)
>
> but I still get the type mismatch.
>
> I have also done
> MsgBox strTmp
> Just to confirm it really looks like a 10 digit number (and it does).
>
> I've come accross a oddities like this before where vbScript code
> that's happy on one machine gives type mismatches on another...
>
> Any clues as to why?
>
> Tim.
>
>
>
>
>
>

Tim
Fri Sep 07 07:13:31 PDT 2007

Ahh, I figured it out.
When pasting your code into TextPad, I got '-' signs in the Const E
hence the type mismatch errors. Oops, maybe you meant something when
you said 'Watch line wrapping', sorry ;).

Anyway, I was puzzled that your version appeared to run slower than
mine, and was giving a wide range of times from 0.7 - 3 seconds, then
I noticed that
you were also testing how fast a user could press the 'ok button' (I
guess you were running it in CScript rather than WScript and so didn't
have this issue)

If (blnPrime = True) Then
Wscript.Echo dblCandidate
lngEnd = Timer()
Wscript.Echo "Time required: " & CStr(lngEnd - lngStart)
Wscript.Quit
End If

By moving the lngEnd = Timer() line to before the Wscript.Echo Line,
yours now runs in about 0.07 seconds on my hardware, whereas my
version (using Option Explicit and Dimming the variables) runs in
about 0.27 and about 0.47 seconds without using Option Explicit.

Tim

Richard
Fri Sep 07 08:09:26 PDT 2007

I always use cscript and run scripts at a command prompt. If I have time I
want to see if the sieve can be made more efficient. I developed the basic
algorithm I use long ago for a very slow programmable calculator. I also
used it in assembly language programs to factor 64-bit numbers on 32-bit
computers. It's crude, but works well on smaller numbers (up to 2^64).

--
Richard Mueller
Microsoft MVP Scripting and ADSI
Hilltop Lab - http://www.rlmueller.net
--

"Tim" <TimJordanVBS@hotmail.com> wrote in message
news:1189174411.337314.181600@r29g2000hsg.googlegroups.com...
> Ahh, I figured it out.
> When pasting your code into TextPad, I got '-' signs in the Const E
> hence the type mismatch errors. Oops, maybe you meant something when
> you said 'Watch line wrapping', sorry ;).
>
> Anyway, I was puzzled that your version appeared to run slower than
> mine, and was giving a wide range of times from 0.7 - 3 seconds, then
> I noticed that
> you were also testing how fast a user could press the 'ok button' (I
> guess you were running it in CScript rather than WScript and so didn't
> have this issue)
>
> If (blnPrime = True) Then
> Wscript.Echo dblCandidate
> lngEnd = Timer()
> Wscript.Echo "Time required: " & CStr(lngEnd - lngStart)
> Wscript.Quit
> End If
>
> By moving the lngEnd = Timer() line to before the Wscript.Echo Line,
> yours now runs in about 0.07 seconds on my hardware, whereas my
> version (using Option Explicit and Dimming the variables) runs in
> about 0.27 and about 0.47 seconds without using Option Explicit.
>
> Tim
>
>
>
>

Anthony
Fri Sep 07 09:03:30 PDT 2007

"Richard Mueller [MVP]" <rlmueller-nospam@ameritech.nospam.net> wrote in
message news:%23KpjT7L8HHA.1444@TK2MSFTNGP05.phx.gbl...
> I found a better way to generate the sequence I was talking about. This
> version takes about 0.11 seconds (instead of 0.14 in the previous
example).
> For each 10 digit number, the program checks if the number is prime by
> trying all possible factors in the sequence:
>
> 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 49, 53, ...
>
> up to the square root of the number. It avoids all divisors after the
first
> few that are multiples of 2, 3, or 5.
> ================
> Option Explicit
>
> Dim lngStart, k, dblCandidate, dblFactor, dblLimit, dblTemp, blnPrime
> Dim lngEnd, arrIncr, j
>
> Const E =
>
"271828182845904523536028747135266249775724709369995957496696762772407663035
3547594571382178525166427427466391932003059921817413596629043572900334295260
5956307381323286279434907632338298807531952510190115738341879307021540891499
3488416750924476146066808226480016847741185374234544243710753907774499206955
1702761838606261331384583000752044933826560297606737113200709328709127443747
0472306969772093101416928368190255151086574637721112523897844250569536967707
85449969967946864454905987931636889230098793"
>
> lngStart=Timer()
>
> ' Sequence to increment divisors.
> ' The sequence 4, 2, 4, 2, 4, 6, 2, 6 is repeated.
> arrIncr = Array(1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6)
>
> For k = 1 To Len(E) - 9
> dblCandidate = CDbl(Mid(E, k, 10))
> dblLimit = Fix(Sqr(dblCandidate))
>
> blnPrime = True
> dblFactor = 2
> j = 0
> Do Until (dblFactor > dblLimit)
> dblTemp = dblCandidate / dblFactor
> If (dblTemp = Fix(dblTemp)) Then
> ' Factor found
> blnPrime = False
> Exit Do
> End If
> dblFactor = Round(dblFactor + arrIncr(j))

dblFactor is always an integer, why Round?

> j = j + 1
> If (j > 10) Then
> j = 3
> End If
> Loop
>
> If (blnPrime = True) Then
> Wscript.Echo dblCandidate
> lngEnd = Timer()

The reported time required depends on how quickly you can press the OK
button to dismiss the message box when not using the command line. ;) Swap
the lines above.

> Wscript.Echo "Time required: " & CStr(lngEnd - lngStart)
> Wscript.Quit
> End If
> Next
> Wscript.Echo "No primes found"
> lngEnd = Timer()
> Wscript.Echo "Time required: " & CStr(lngEnd - lngStart)
>



--
Anthony Jones - MVP ASP/ASP.NET

Tim
Fri Sep 07 09:09:31 PDT 2007

Let me know if you find any nifty shortcuts in producing the sieve!
Main thing I found (actually a friend pointed it out) is that you only
need to work through the array up to the squareroot of the length of
the array (any non-primes past this point will have already been
'crossed off' by an earlier prime).

Also, once the sieve stage is done, and we are onto attempting to find
a divisor for a 10 digit candidate, I found it was quicker to work
against the sieve array directly and just ignore the non-primes,
rather than to dump the 9000 or so primes out to a new array.

Tim

Richard
Fri Sep 07 12:08:15 PDT 2007

See inline below:

"Anthony Jones" <Ant@yadayadayada.com> wrote in message
news:eTMljiW8HHA.1184@TK2MSFTNGP04.phx.gbl...
> "Richard Mueller [MVP]" <rlmueller-nospam@ameritech.nospam.net> wrote in
> message news:%23KpjT7L8HHA.1444@TK2MSFTNGP05.phx.gbl...

...snip

>> blnPrime = True
>> dblFactor = 2
>> j = 0
>> Do Until (dblFactor > dblLimit)
>> dblTemp = dblCandidate / dblFactor
>> If (dblTemp = Fix(dblTemp)) Then
>> ' Factor found
>> blnPrime = False
>> Exit Do
>> End If
>> dblFactor = Round(dblFactor + arrIncr(j))
>
> dblFactor is always an integer, why Round?

I don't like working with doubles in cases like this. I'm trying make sure
it is an integer, but thinking about it the Round won't help. I know the
program worked fine before I added it.

>
>> j = j + 1
>> If (j > 10) Then
>> j = 3
>> End If
>> Loop
>>
>> If (blnPrime = True) Then
>> Wscript.Echo dblCandidate
>> lngEnd = Timer()
>
> The reported time required depends on how quickly you can press the OK
> button to dismiss the message box when not using the command line. ;)
> Swap
> the lines above.
>

The program was intended to be run at a command prompt with the cscript
host, so no acknowledgement of an OK button is required. It wasn't an issue
for me when I tested, but I should have reversed the statements.

--
Richard Mueller
Microsoft MVP Scripting and ADSI
Hilltop Lab - http://www.rlmueller.net
--

Dr
Sun Sep 09 15:24:41 PDT 2007

In microsoft.public.scripting.vbscript message <uD433JY8HHA.4880@TK2MSFT
NGP03.phx.gbl>, Fri, 7 Sep 2007 14:08:15, "Richard Mueller [MVP]"
<rlmueller-nospam@ameritech.nospam.net> posted:

>I don't like working with doubles in cases like this.

Strictly-integer calculations with Doubles should be perfectly reliable
if a magnitude of 2^53 cannot be exceeded. Javascript works, using
Doubles for everything.

It's a good idea to read the newsgroup c.l.j and its FAQ. See below.

--
(c) John Stockton, Surrey, UK. ?@merlyn.demon.co.uk Turnpike v6.05 IE 6
news:comp.lang.javascript FAQ <URL:http://www.jibbering.com/faq/index.html>.
<URL:http://www.merlyn.demon.co.uk/js-index.htm> jscr maths, dates, sources.
<URL:http://www.merlyn.demon.co.uk/> TP/BP/Delphi/jscr/&c, FAQ items, links.

Anthony
Mon Sep 10 14:14:06 PDT 2007

"Richard Mueller [MVP]" <rlmueller-nospam@ameritech.nospam.net> wrote in
message news:uD433JY8HHA.4880@TK2MSFTNGP03.phx.gbl...
> See inline below:
>
> "Anthony Jones" <Ant@yadayadayada.com> wrote in message
> news:eTMljiW8HHA.1184@TK2MSFTNGP04.phx.gbl...
> > "Richard Mueller [MVP]" <rlmueller-nospam@ameritech.nospam.net> wrote in
> > message news:%23KpjT7L8HHA.1444@TK2MSFTNGP05.phx.gbl...
>
> ...snip
>
> >> blnPrime = True
> >> dblFactor = 2
> >> j = 0
> >> Do Until (dblFactor > dblLimit)
> >> dblTemp = dblCandidate / dblFactor
> >> If (dblTemp = Fix(dblTemp)) Then
> >> ' Factor found
> >> blnPrime = False
> >> Exit Do
> >> End If
> >> dblFactor = Round(dblFactor + arrIncr(j))
> >
> > dblFactor is always an integer, why Round?
>
> I don't like working with doubles in cases like this. I'm trying make sure
> it is an integer, but thinking about it the Round won't help. I know the
> program worked fine before I added it.
>


Right, I was forgetting how big dblFactor might get.


--
Anthony Jones - MVP ASP/ASP.NET