## prime numbers searcher in QB

User projects written in or related to FreeBASIC.
ron77
Posts: 8
Joined: Feb 21, 2019 19:24

### prime numbers searcher in QB

hi all i'm new here...

here is a code i've written for searching prime numbers from 2 to one million:

Code: Select all

`'\$lang:"qb"'2019-08-17 - developed by ron77 & stxaxtic mod B+'_TITLE "PRIME NUMBER FINDER"DO    PRINT "press ESC key while program running to exit search"    INPUT "Choose Upper value to search up to 1,000,000: ", n    IF n > 1000000 THEN n = 1000000    count = 0    pause = 0    total = 0    FOR l = 2 TO n        f = -1        k\$ = INKEY\$        total = total + 1        FOR m = 2 TO INT(SQR(l))            IF l / m = l \ m THEN                f = 0                EXIT FOR            END IF        NEXT        IF f THEN            count = count + 1            PRINT STR\$(l) + ", ";            pause = pause + 1            IF pause = 100 THEN PRINT: PRINT: PRINT "TOTAL NUMBERS SCAN SO FAR: " + STR\$(total) + " PRIME NUMBERS FOUND SO FAR: " + STR\$(count): PRINT: SLEEP (4): pause = 0 'OK better reset and do increments of 100        END IF        IF k\$ = CHR\$(27) THEN EXIT FOR    NEXT    PRINT    PRINT: PRINT "TOTAL NUMBERS SCAN :" + STR\$(total) + " TOTAL PRIME NUMBERS FOUND: " + STR\$(count): PRINT    PRINTLOOP`
integer
Posts: 385
Joined: Feb 01, 2007 16:54
Location: usa

### Re: prime numbers searcher in QB

Welcome to the site.

I do not recall seeing the double divide before: the floating point & whole number division. That is a different approach.
Most would use the shorter (quicker) mod instruction.
Nice attempt. Keep up the good work.

If speed is what you would like to see, several members have written fast prime number generators.
One of the routines generated 10 million primes in about 3 seconds.
integer
Posts: 385
Joined: Feb 01, 2007 16:54
Location: usa

### HOW & WHY does cpp Optimize better than FreeBasic?

at this website
https://www.codeproject.com/Tips/5254588/Simple-Prime-Number-Calculator-Cplusplus
Fabrizio Civetta stated that his cpp program can generate the primes less that 2million is about 6 seconds.
When I converted his cpp program to FreeBasic it required about 90 seconds to compute the primes less that 2 million.
This is the cpp code converted to FreeBasic:
to avoid direct copyright infringement, the variables were renamed (somewhat) and I replaced the 'GOTO' with a DO/LOOP structure.

Code: Select all

`    dim as long mx = 2000000    ''= 2 million takes 90seconds    dim as long w(mx)    dim as long wn(mx)    dim as long cnt = 1    dim as long wi = 0    dim as long i    dim as double t2, t1    t1 = timer    DO        cnt = cnt + 2        for i = 1 to wi            if (w(i) < cnt) THEN w(i) +=  wn(i)            if (w(i) = cnt) then CONTINUE DO        next i        if (cnt > mx) THEN exit do        wi += 1        wn(wi) = cnt        w(wi) = cnt    LOOP        t2 = timer    print t2-t1;" seconds to generate Primes below ";mx    for i=0 to 20        print wn(i);" ";    next i    getkey`

My question is: How can cpp optimize the code to run in 6 seconds while FB code requires 90 seconds?
The specific algorithm here is not as fast as some code posted previously on this forum.
That other code will generate the prime numbers less that 1.2 BILLION is about 1/2 minute.
The quickness of the method is not what bothers me.

Is there any one who can give a hint as to how cpp does such a fantastic optimization?
I do not know and cannot guess as to how it is possible.
FreeBasic: 90 seconds
cpp: 6 seconds
D.J.Peters
Posts: 7949
Joined: May 28, 2005 3:28

### Re: prime numbers searcher in QB

"2.000.000 of numbers in 6 seconds on single core I7 3 Ghz."
may be should be:
"2.000.000 of numbers in 60 seconds on single core I7 3 Ghz."

FreeBASIC. 51 seconds !

note: C/CPP array's are pointers not an struct like a FreeBASIC array !

Joshy
fxm
Posts: 9477
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

### Re: prime numbers searcher in QB

26 seconds on my PC intel CORE i7 (gas win32).
srvaldez
Posts: 2239
Joined: Sep 25, 2005 21:54

### Re: prime numbers searcher in QB

after changing the cpp _int64 to __int64 and using -O2 the runtime is 7 seconds
changing the FB code from long to longint and compiling with FBx64 -gen gcc -O 2 the runtime is 4.5 seconds
integer
Posts: 385
Joined: Feb 01, 2007 16:54
Location: usa

### Re: prime numbers searcher in QB

@D.J.Peters
@fxm
@srvaldez

So, instead of a working class race horse on my desk, I have a mule.
Your response is very much appreciated.

Thank you.
dodicat
Posts: 6163
Joined: Jan 10, 2006 20:30
Location: Scotland

### Re: prime numbers searcher in QB

Hi integer.
Over there in a classless society where you can aspire to great heights by merit alone, (The land of the free e..t.c. ...), a working class horse I believe can become a racehorse.
Over here in this class ridden pit a working class horse is condemned to pulling a plough from dawn til disk, or sent to the city to work for for some ruthless rag and bone merchant or condemned for life to some other back breaking trade.
Race horses over here are born into wealthy stables, fed with silver embroidered nosebags, and very many achieve great status.
(This is completely off topic and has little to do with prime numbers, so I apologise).

Here is a quick generator, not as quick as the Sieve of Eratosthenes, but it extends into ulongint if required.

Code: Select all

`Function isprime(n As Ulongint) As integer    If (n=2) Or (n=3) Then Return -1    If n Mod 2 = 0 Then return 0    If n Mod 3 = 0 Then return 0    Dim As Ulongint limit=Sqr(N)+1    For I As Ulongint = 6 To limit Step 6        If N Mod (i-1) = 0 Then return 0        If N Mod (i+1) = 0 Then return 0    Next I    Return -1End Functiondim as double t1=timer,t2dim as long num=2000000,counterredim as ulongint primes(1 to num\2)for n as long=1 to num    if isprime(n) then        counter+=1        primes(counter)=n    end ifnext nredim preserve primes(1 to counter)t2=timerfor n as long=1 to 20    print primes(n)nextprint ". . ."print ". . ."for n as long=ubound(primes)-20 to ubound(primes)    print primes(n)nextprintprint t2-t1sleep `

If you step n by 2 (as usual for primes by division), then it is slower for some strange reason, and of course misses out 2.
integer
Posts: 385
Joined: Feb 01, 2007 16:54
Location: usa

### Re: prime numbers searcher in QB

If you step n by 2 (as usual for primes by division), then it is slower for some strange reason, and of course misses out 2.

If it steps by two, there is no call/return to the function -- it should be faster. But it is not.

Over here, we have a bunch of donkeys and mules, who have no class what so ever,
who are trying to convince everyone that they are race horses worthy of coronation.
Obviously, that is an observation about computer science and programming.
There are some who may misunderstand that comment to imply something else.

Your code (that finds the primes less than 2 million) runs in 0.56 seconds on my PC (ok snail)
dodicat
Posts: 6163
Joined: Jan 10, 2006 20:30
Location: Scotland

### Re: prime numbers searcher in QB

Integer.
Your c++ code takes 73 seconds here:

Code: Select all

`Started! to:20000002000003Wall time passed: 73 s.Press any key to continue . . . `

I used Dev c++, g++ from Mingw wouldn't compile it.
#include <stdlib.h>
#define _int64 long long
#define nullptr 0
to the C++ code.
Here is a standard Sieve of Eratosthenes.
(Been coded many times before in fb in slightly different ways)

Code: Select all

` Sub generateprimes(primes() as integer,nmax as integer)    redim primes(1 to nmax)   var np = 0    Dim As Integer i, k    For k = 2 To nmax        If primes(k) = 0 Then            np += 1            primes(np) = k            For i = 2*k To nmax Step k                primes(i) = 1            Next i        End If    Next k    Redim Preserve primes(1 to np)End Subdim as double t1=timer,t2redim as integer p()generateprimes(p(),2000000)t2=timerfor n as long=1 to 20    print p(n)nextprint ". . ."print ". . ."for n as long=ubound(p)-20 to ubound(p)    print p(n)nextprintprint t2-t1sleep `

Thanks for your original code ron77