Nobel Prize will not receive itself
Nobelevskaya premiya sama sebya ne poluchit
Нобелевская премия сама себя не получит
Le prix Nobel ne se recevra pas
Nobelpreis wird sich nicht erhalten
Il Premio Nobel non ricevera se stesso
Write name of program in 1st line to copy & paste & save filename.bas
Insert program pictures: press print-screen-shot button
Open paint & Paste & Save as PNG
Add picture file to program topic
Russia looks world from future. Big data is peace data.
I never recommend anything & always write only about myself
05-02-2022, 12:49 PM (This post was last modified: 05-02-2022, 12:50 PM by DANILIN.)
I am currently a PeaceMaker
I applied to Ministries of RF and to deputies
and received answers and notifications
But I don't write about political topics anywhere
so that my appeals to authorities are not discussed
And I recommend 2020 movie: TeNeT
Flagimation: 137 kB
Write name of program in 1st line to copy & paste & save filename.bas
Insert program pictures: press print-screen-shot button
Open paint & Paste & Save as PNG
Add picture file to program topic
Russia looks world from future. Big data is peace data.
I never recommend anything & always write only about myself
plus I recommend quick documents indexing
and search within a few seconds
since 2005 Archivarius 3000
likasoft.com/document-search/index-en.shtml
further: algorithms against falsification of randomness
are specially designed for a minimum of pictures
even small ones
Write name of program in 1st line to copy & paste & save filename.bas
Insert program pictures: press print-screen-shot button
Open paint & Paste & Save as PNG
Add picture file to program topic
Russia looks world from future. Big data is peace data.
I never recommend anything & always write only about myself
06-06-2022, 03:15 PM (This post was last modified: 06-06-2022, 10:21 PM by DANILIN.)
10001th prime
Find and show: 10001st prime number
rosettacode.org/wiki/10001th_prime
qbasic
Code: (Select All)
max = 10001: n=0: s=1 ' PRIMES.bas
While n <= max ' 10001 104743 3 seconds
f=0
For j=2 To s^0.5
If s Mod j = 0 Then f=1
Next
If f=0 Then n = n+1
s = s+1
Wend
Print n-1, s-1
Python
Code: (Select All)
import time; max=10001; n=1; p=1; # PRIMES russian DANILIN
while n<=max: # 10001 104743 5 seconds
f=0; j=2 # rextester.com/AHEH3087
while f < 1:
if j >= int(p**0.5):
f=2
if p % j == 0:
f=1
j+=1
if f != 1:
n+=1;
#print(n,p);
p+=2
print(n-1,p-2)
print(time.perf_counter())
C#
Code: (Select All)
using System; using System.Text; // PRIMEQ.cs
namespace p10001 // 1 second 10001 104743
{ class Program // rextester.com/YXNR89875
{ static void Main(string[] args)
{ int max=10001; int n=1; int p=1; int f; int j;
while (n <= max)
{ f=0; j=2;
while (f < 1)
{ if (j >= Convert.ToInt32(Math.Pow(p,0.5)))
{ f=2; }
if (p % j == 0) { f=1; }
j++;
}
if (f != 1) { n++; } // Console.WriteLine("{0} {1}", n, p);
p++;
}
Console.Write("{0} {1}", n-1, p-1);
Console.ReadKey();
}}}
qb64
Code: (Select All)
max=10001: n=1: p=0: t=Timer ' PRIMES.bas
While n <= max ' 10001 104743 0.35 seconds
f=0: j=2
While f < 1
If j >= p^0.5 Then f=2
If p Mod j = 0 Then f=1
j=j+1
Wend
If f <> 1 Then n=n+1: ' Print n, p
p=p+1
Wend
Print n-1, p-1, Timer-t
Your Answers ?! ?!
Write name of program in 1st line to copy & paste & save filename.bas
Insert program pictures: press print-screen-shot button
Open paint & Paste & Save as PNG
Add picture file to program topic
Russia looks world from future. Big data is peace data.
I never recommend anything & always write only about myself
06-07-2022, 12:51 PM (This post was last modified: 06-07-2022, 12:53 PM by bplus.)
6 Wheel Sieve 78498 primes from first million integers in .046 secs
Code: (Select All)
_Title "6 Wheel Sieve"
' 6 wheel sieve.bas for QB64 fork (B+=MGA) 2017-08-30 copy and trans to QB64
'translated from: First Factors.bas for SmallBASIC 11/27/14 (bpf.org post)
'topN = 1000000, primes 78,498, .17 secs, 8169 twins last 999959, 999961
'topN = 10000000, primes 664,579, 1.85 secs, 58,980 twins last 9999971, 9999973
'topN = 100000000, primes 5,761,455, 20.69 secs, 440,312 twins last 99999587, 99999589
' out of memory for 1 billion
'compare to 30 wheel
'topN = 1000000, primes 78,498, .15 secs, 8169 twins last 999959, 999961
'topN = 10000000, primes 664,579, 1.81 secs, 58,980 twins last 9999971, 9999973
'topN = 100000000, primes 5,761,455, 19.65 secs, 440,312 twins last 99999587, 99999589
' out of memory for 1 billion
'compare to 2310 wheel sieve WOW the 30 wheel is faster!
'QB64 results from 2310 wheel
'topN = 1000000, primes 78,498, .18 secs, 8169 twins last 999959, 999961
'topN = 10000000, primes 664,579, 1.98 secs, 58,980 twins last 9999971, 9999973
'topN = 100000000, primes 5,761,455, 21.57 secs, 440,312 twins last 99999587, 99999589
' out of memory for 1 billion
_Define A-Z As _INTEGER64
Option Base 1
Common Shared ff(), topN
topN = 1223 'first 200 primes test
topN = 1000000
testlimitN = Sqr(topN)
'First Factors array is 0 for prime number or contains the numbers lowest factor
Dim ff(topN + 6)
tStart# = Timer(.001)
For i = 0 To topN Step 6
ff(i + 2) = 2: ff(i + 3) = 3: ff(i + 4) = 2: ff(i + 6) = 2
Next
ff(2) = 0: ff(3) = 0 'fix first 2 factors
For pcand = 5 To testlimitN Step 2
If ff(pcand) = 0 Then
For i = pcand * pcand To topN Step 2 * pcand
If ff(i) = 0 Then ff(i) = pcand
Next
End If
Next
'count primes
For i = 2 To topN
If ff(i) = 0 Then p = p + 1
Next
tStop# = Timer(.001)
tTime# = tStop# - tStart#
Print "For "; topN; " numbers there are "; p; " primes in "; tTime#; " secs."
If 0 Then ' <<<<< uncomment this as needed
'file twin primes data
Open "Twin primes.txt" For Output As #1
lastp = -1
For i = 2 To topN
If ff(i) = 0 Then
If i - lastp = 2 Then
Print #1, Str$(lastp) + ", " + Str$(i) + " Middle/6 = " + Str$((i - 1) / 6) + ": " + factors$((i - 1) / 6)
tCount = tCount + 1
End If
lastp = i
End If
Next
Close #1
Print "Found "; tCount; " Twin Primes in first "; topN; " integers."
End If ' <<<<<<<<<<<<< uncomment this as needed
'test some factoring of numbers
factorMe = 10
While factorMe > 1
Input "Enter a number to factor, 0 quits "; factorMe
If factorMe < 2 Then Exit While Else Print factors$(factorMe)
Wend
Function factors$ (n)
If n > topN Then factors$ = "Error: too high a number.": Exit Function
f$ = ""
While ff(n) <> 0
f$ = f$ + Str$(ff(n)) + " "
n = n / ff(n)
Wend
factors$ = f$ + Str$(n)
End Function
(06-06-2022, 03:15 PM)DANILIN Wrote: 10001th prime
Find and show: 10001st prime number
rosettacode.org/wiki/10001th_prime
qbasic
Code: (Select All)
max = 10001: n=0: s=1 ' PRIMES.bas
While n <= max ' 10001 104743 3 seconds
f=0
For j=2 To s^0.5
If s Mod j = 0 Then f=1
Next
If f=0 Then n = n+1
s = s+1
Wend
Print n-1, s-1
Python
Code: (Select All)
import time; max=10001; n=1; p=1; # PRIMES russian DANILIN
while n<=max: # 10001 104743 5 seconds
f=0; j=2 # rextester.com/AHEH3087
while f < 1:
if j >= int(p**0.5):
f=2
if p % j == 0:
f=1
j+=1
if f != 1:
n+=1;
#print(n,p);
p+=2
print(n-1,p-2)
print(time.perf_counter())
C#
Code: (Select All)
using System; using System.Text; // PRIMEQ.cs
namespace p10001 // 1 second 10001 104743
{ class Program // rextester.com/YXNR89875
{ static void Main(string[] args)
{ int max=10001; int n=1; int p=1; int f; int j;
while (n <= max)
{ f=0; j=2;
while (f < 1)
{ if (j >= Convert.ToInt32(Math.Pow(p,0.5)))
{ f=2; }
if (p % j == 0) { f=1; }
j++;
}
if (f != 1) { n++; } // Console.WriteLine("{0} {1}", n, p);
p++;
}
Console.Write("{0} {1}", n-1, p-1);
Console.ReadKey();
}}}
qb64
Code: (Select All)
max=10001: n=1: p=0: t=Timer ' PRIMES.bas
While n <= max ' 10001 104743 0.35 seconds
f=0: j=2
While f < 1
If j >= p^0.5 Then f=2
If p Mod j = 0 Then f=1
j=j+1
Wend
If f <> 1 Then n=n+1: ' Print n, p
p=p+1
Wend
Print n-1, p-1, Timer-t
Your Answers ?! ?!
That's pretty much the way I would do it, so no major changes, but....
What stands out to me is that the value of p does not change within the inner loop, therefore repeating the exponential operation "p ^ 0.5" within the inner loop is slowing the program down. Moving "p ^ 0.5" to the outer loop doubles the speed of the program:
Code: (Select All)
'JRace's results:
'Original version: 10001 104743 .21875
'This version: 10001 104743 .109375
max = 10001: n = 1: p = 0: t = Timer ' PRIMES.bas
While n <= max ' 10001 104743 0.35 seconds
f = 0: j = 2
pp = p ^ 0.5 'NEW VAR: move exponentiation here, to outer loop
While f < 1
'If j >= p ^ 0.5 Then f = 2 'original line
'NOTE: p does not change in this loop,
' therefore p^0.5 doesn't change;
' moving p^0.5 to the outer loop will eliminate a lot of FP math)
If j >= pp Then f = 2 'new version with exponentiation relocated
If p Mod j = 0 Then f = 1
j = j + 1
Wend
If f <> 1 Then n = n + 1: ' Print n, p
p = p + 1
Wend
Print n - 1, p - 1, Timer - t
I'm sure the other versions of the program will also give much better times if you make similar changes to their inner loops.
06-07-2022, 09:32 PM (This post was last modified: 06-08-2022, 09:06 PM by JRace.
Edit Reason: missing paren
)
(06-06-2022, 03:15 PM)DANILIN Wrote: 10001th prime
Find and show: 10001st prime number
rosettacode.org/wiki/10001th_prime
Okay, you made me think.
I dusted off an old Sieve of Eratosthenes program I had lying around.
Problem is: the original version of the program has no quick-and-easy way to stop when prime 10001 is found.
SO, I tweaked the buffer size so that ONLY 10001 primes will fit.
(Edit: OK, NOW there is a way to catch and print the nth prime: set the "target" constant to be your chosen target.
This ALSO means you can go hog wild and increase the size of the prime flag buffer to any size you want, if the compiler is OK with it, by changing the "size" constant.)
This thing runs so fast that my run times keep coming out at 0.0 seconds, to I've set this version to run the Sieve loop 100 times to give a meaningful run time.
Is it cheating to use a sieve to improve speed? The RosettaCode rules say nothing about it. Of course the rules say nothing about speed requirements, either.
Code: (Select All)
Rem DMDScript demo.
Rem Lightly modified to make it easier to change the number of iterations.
Rem QB64 & FreeBASIC (in QB compatibility mode) port
Rem This version is built to find and display the 10,001st prime, per DANILIN's RosettaCode challenge.
Print "Eratosthenes Sieve prime number calculation"
Const iters = 100
Dim Shared flags(sizepl) As Integer 'SHARED not needed for QB64
Const true = 1
Const false = 0
Const target = 10001
Print iters; " iterations": Print
starttime = Timer
For iter = 1 To iters
count = 0
For i = 0 To size
flags(i) = true
Next
For i = 0 To size
If flags(i) = true Then
prime = i + i + 3
k = i + prime
While k <= size
flags(k) = false
k = k + prime
Wend
count = count + 1
If (count = target) And (printed = false) Then
Print "Prime "; target; " is: "; prime: Print
printed = true
End If
End If
Next
Next
elapsedtime = Timer - starttime
Print count; " primes in the range of 3 to "; size + size + 3
Print
Print "elapsed time = ";: Print Using "##.#####"; elapsedtime
Print "time per iteration = ";: Print Using "##.#####"; elapsedtime / iters
'Sleep 'Prevent the program window from closing immediately
Prime 10001 is: 104759
Time for 100 iterations: 0.38477
Time per iteration: 0.00385
(Edited to add: Doh! I didn't actually show the 10001st prime with this one. Fixed.)
This was a nice catch on Danilin's code:
If j >= p ^ 0.5 Then f = 2 'original line moved outside inner loop
But as far as speed goes, sieving is way faster than testing so many times for divisibility with MOD. But you need an array to save results. Maybe the RC challenge was looking to do it without arrays? BUT who really needs to know the 10001th dang prime number? or any nth prime number. Most applications use primes info for factoring so you need to collect prime info in an array for vast range of factors and sieving is fastest for that to do something more practical than this RC challenge.
Sieving with wheels is even faster! The example I showed was sieving with a wheel of 6 the samllest, which takes out all multiples of 2 and 3 for prime candidates even before you start sieving. That's 1/2 of all numbers plus 1/3 of 1/2 = 1/6 of the remaining prime candidates.
Sieving with a 210 wheel; takes out 2, 3, 5, 7 multiples (2*3*5*7 = 210) before sieving with remaining prime candidates another speed improvement. The wheel size eventually get unwieldy but it depends on the number of integers your prime info (what I call array or first factors) needs to cover.
This was a nice catch on Danilin's code:
If j >= p ^ 0.5 Then f = 2 'original line moved outside inner loop
But as far as speed goes, sieving is way faster than testing so many times for divisibility with MOD. But you need an array to save results. Maybe the RC challenge was looking to do it without arrays? BUT who really needs to know the 10001th dang prime number? or any nth prime number. Most applications use primes info for factoring so you need to collect prime info in an array for vast range of factors and sieving is fastest for that to do something more practical than this RC challenge.
Sieving with wheels is even faster! The example I showed was sieving with a wheel of 6 the samllest, which takes out all multiples of 2 and 3 for prime candidates even before you start sieving. That's 1/2 of all numbers plus 1/3 of 1/2 = 1/6 of the remaining prime candidates.
Sieving with a 210 wheel; takes out 2, 3, 5, 7 multiples (2*3*5*7 = 210) before sieving with remaining prime candidates another speed improvement. The wheel size eventually get unwieldy but it depends on the number of integers your prime info (what I call array or first factors) needs to cover.
Re the catch: I started programming in the days of 8-bit, 64K max CPUs, when RAM was at a premium and even integer multiplies and divides were expensive, cycle-wise, so my eye is trained to spot little inefficiencies.
The RCode (I hesitate to use the initials RC on this site) page has no rules yet. It's not even a challenge at this point:
Quote:10001th prime is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
10001th prime
Task
Find and show on this page the 10001st prime number.
The sieve I posted leaves out multiples of 2 by design, but I've never (yet) experimented with wheels. I had thought about preemptively marking off the lower primes, but wasn't sure about the benefit and never even bothered. You introduced me to the term "wheels" in this usage.
The prog I posted was one of MANY translations I made of an example program from the Digital Mars website. After checking out DMDScript's speed (it may do well against older JavaScript engines, but it can't hold a candle to SpiderMonkey or V8), I went on a speed testing binge of several different compilers & interpreters. Granted, a sieve is not a well-rounded benchmark, but it was an amusing diversion (especially during slow times at work) until I got bored with it.
I've been programming mainly in C for many years and am weary of doing all the little things that one must do, over and over again, to craft a robust C program. I wanted a simpler way of creating small utilities and such on the fly. Anyway, my experiments led me to learn and use GAWK for a while, but I eventually came back home to Basic.
![[Image: flusausrukfr.gif]](http://kenokeno.ucoz.ru/flag/flusausrukfr.gif)
