Qbasicnews.com
January 27, 2021, 08:13:56 AM
 Pages: 1 2 [3] 4 5
 Author Topic: The PRIME NUMBERS  (Read 32207 times)
Antoni Gual
Na_th_an

Posts: 1434

 « Reply #30 on: June 02, 2003, 08:48:49 PM »

Well, actually I could do it faster:
-Limited size of tables so they fit in dgroup.
-Saves primes into a file so you can check them
-It displays one prime every 16000 so you can see it's working
-It calculates and saves 300,000 primes in 1 minute (compiled)
The highest prime it can calculate should be under 2^30, it makes around 5,000,000 primes. However,I have not patiented to see the end , it can take hours and probably it ends by an error.

Code:

CLS
PRINT "PRIME CALCULATOR BY ANTONI GUAL agual@eic.ictnet.es"
'Version 2.
CONST pp = 1024& * 16 - 1

CONST stor = 3400 'enough to calculate the 10,000,000 first primes
DIM pr(stor + 2) AS INTEGER
DIM pr1(stor + 2) AS LONG
DIM pr2(stor + 2) AS LONG
DIM ind AS LONG

'pr saves primes found
'pr1 saves primes multiplied by factor pr2
'We save pr2 to stop scanning the array if pr2<pr, this indicates that
' pr> sqr(test&) without having to calculate the square root.
'
'pr() saves primes, pr1()=pr()*pr2()

'init the tables with 3 and test our first candidate, 5
pr(2) = 3
pr1(2) = 3
pr2(2) = 1
maxx& = 2
ind = 2
test& = 5

t! = TIMER
OPEN "primes.txt" FOR OUTPUT AS #1
PRINT #1, 2, 3,
DO
isprime% = -1
i% = 1
DO
i% = i% + 1
WHILE pr1(i%) < test&: pr1(i%) = pr1(i%) + pr(i%): pr2(i%) = pr2(i%) + 1: WEND
IF pr1(i%) = test& THEN isprime% = 0: EXIT DO
LOOP UNTIL pr2(i%) <= pr(i%)
IF isprime% THEN
ind = ind + 1
IF (ind AND pp) = 0 THEN PRINT USING "####### th prime is: ##########. Time:###.# sec."; ind; test&; TIMER - t!
PRINT #1, test&,
IF (ind AND 7) = 0 THEN PRINT #1,
IF ind <= stor THEN
pr(ind) = test&
pr1(ind) = test&
pr2(ind) = 1
END IF
END IF
test& = test& + 2
LOOP UNTIL (i% = stor) OR LEN(INKEY\$)
ERASE pr, pr1, pr2
CLOSE
 Logged

Antoni
Mango
Wandering Guru

Posts: 360

 « Reply #31 on: June 02, 2003, 09:21:06 PM »

Quote from: "Antoni Gual"
Let's try it in the spanish way:
The best way to calculate a square root is not calculating it at all..
No divisions or MOD either..
It calculates 16384 primes in 3 seconds in my P4 1,4... to display them it takes a little longer.

Antonio...note that in my May 7 post, I used a similar method to avoid the sqrt issue ...using 2 different methods for the big primes and for the small primes:

1st
LOOP WHILE smallprimes(a) * smallprimes(a) < next1

2nd
LOOP WHILE (nextbig& \ smallprimes(a)) > smallprimes(a)

I used the 2nd method because the numbers got too big when the direct square was used.

However, when I tweaked the code a bit in my May 29 post...I used SQR...outside the loop.  which turned out to be faster.   Also, by using a separate array to hold the small primes you don't have the problem of overflow errors...and if you hold the small primes as integers (for the ones smaller than 32000) and use these to test the long integer primes, both save memory and gain on speed.

OT...I looked at your file handling routines last week...thanks.

To the people just now posting their prime-finding methods...just to make sure we are all on the same page, as the recent methods haven't been printing all the primes (even though they were calculated), if you want to see if your method is a contender, make it print all primes using the semicolon...eg:
PRINT myprime&;

and compare the output to the output of the following code by Me and  Argamemnus:
In the iteration before this, the code just printed one prime every second...which is a convienient way to see the highest prime that will be printed in, say, 10 seconds.  However, this may be confusing to those just joining the fray...

I'm sure we'd all love to see a faster method than this...

Code:
DIM prime(1 TO 5000) AS INTEGER, cur.prime.amount AS INTEGER
cur.prime.amount% = 1
prime%(1) = 2
i% = 3
1 j% = 0
sqrt.num% = SQR(i%)
2 j% = j% + 1
temp% = prime%(j%)
IF i% MOD temp% = 0 THEN GOTO 4
IF temp% >= sqrt.num% THEN GOTO 3
GOTO 2
3 cur.prime.amount% = cur.prime.amount% + 1
prime%(cur.prime.amount%) = i%: PRINT i%;
4 IF i% = 32767 THEN GOTO 5
i% = i% + 2
GOTO 1
5 i2& = prime(cur.prime.amount%)
i2& = i2& + 2
biggest.prime& = i2&
6 j% = 1
sqrt.num% = SQR(i2&)
7 temp% = prime(j%)
IF i2& MOD temp% = 0 THEN GOTO 9
IF temp% >= sqrt.num% THEN GOTO 8
j% = j% + 1
GOTO 7
8 PRINT i2&;
9 i2& = i2& + 2
GOTO 6

Argamemnus...is this post OK that I give shared credit for the code?  If not, I'll erase the whole thing...

Cheers, and thanks for the tips, people.
 Logged
Antoni Gual
Na_th_an

Posts: 1434

 « Reply #32 on: June 02, 2003, 09:37:58 PM »

Well this one abides by all rules set by Touf:
-You can set the maximum prime you want
-It prints them all (after saving them into a file)
Code:

CLS
PRINT "PRIME CALCULATOR BY ANTONI GUAL agual@eic.ictnet.es"
INPUT "Maximum prime(1 to 1,000,000,000): "; mp&

CONST pp = 1024& * 16 - 1
CONST tabs = 10
CONST stor = 3400 'enough to calculate the 10,000,000 first primes
DIM pr(stor + 2) AS INTEGER
DIM pr1(stor + 2) AS LONG
DIM pr2(stor + 2) AS LONG
DIM ind AS LONG

'pr saves primes found
'pr1 saves primes multiplied by factor pr2
'We save pr2 to stop scanning the array if pr2<pr, this indicates that
' pr> sqr(test&) without having to calculate the square root.
'
'pr() saves primes, pr1()=pr()*pr2()

'init the tables with 3 and test our first candidate, 5
pr(2) = 3
pr1(2) = 3
pr2(2) = 1
ind = 2
test& = 5

t! = TIMER
OPEN "primes.txt" FOR OUTPUT AS #1
tt% = tt% + tabs: PRINT #1, 2; TAB(tt%);
tt% = tt% + tabs: PRINT #1, 3; TAB(tt%);
DO
isprime% = -1
i% = 1
DO
i% = i% + 1
WHILE pr1(i%) < test&: pr1(i%) = pr1(i%) + pr(i%): pr2(i%) = pr2(i%) + 1: WEND
IF pr1(i%) = test& THEN isprime% = 0: EXIT DO
LOOP UNTIL pr2(i%) <= pr(i%)
IF isprime% THEN
ind = ind + 1
IF (ind AND pp) = 0 THEN PRINT USING "####### th prime is: ##########. Time:###.# sec."; ind; test&; TIMER - t!
tt% = tt% + tabs: PRINT #1, test&; TAB(tt%);
IF (ind AND 7) = 0 THEN PRINT #1, : tt% = 0
IF ind <= stor THEN
pr(ind) = test&
pr1(ind) = test&
pr2(ind) = 1
END IF
END IF
test& = test& + 2
LOOP UNTIL (i% = stor) OR test& > mp& OR LEN(INKEY\$)
ERASE pr, pr1, pr2
CLOSE
'That's all!
OPEN "primes.txt" FOR INPUT AS #1
WHILE NOT EOF(1)
LINE INPUT #1, a\$
PRINT a\$
WEND
close
PRINT
PRINT "Total time "; TIMER - t!; "seconds. Results are in the file PRIMES.TXT"
 Logged

Antoni
Touf
Member

Posts: 57

 « Reply #33 on: June 03, 2003, 06:07:14 AM »

okay !
I'll chek your programs ( Antoni and Agamemnus ) , and I'll update the classification soon .
 Logged

have the simplest tastes of the World : I satisfy myself with the best !

http://ToufQb.free.fr
Touf
Member

Posts: 57

 « Reply #34 on: June 03, 2003, 09:09:07 AM »

hahaaaa !!!

Agamemnus , your program is quite good , but not enough !  :wink:

I didn't understand the subject of your post ... you said "And the russians beat the french"

Aren't you from USA ?
 Logged

have the simplest tastes of the World : I satisfy myself with the best !

http://ToufQb.free.fr
Agamemnus
x/ \z

Posts: 3491

 « Reply #35 on: June 03, 2003, 01:15:10 PM »

anyways, it is ok to post it, Mango, since your method and mine are almost identical. But be warned! It won't work for any number greater than (the first prime number before 32767) squared!

google.com: primes: first entry: gives a good fast method of finding primes, but the algorithm is incomplete.

Touf: I was born in Moscow, Russia, but I live in the USA.
 Logged

Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
Antoni Gual
Na_th_an

Posts: 1434

 « Reply #36 on: June 03, 2003, 02:51:22 PM »

As I said before the speed problem is not in calculating primes, it is in displaying them.
So there is a version of my algorithm that beats all, just avoiding screen scrolls. Unfortunately Agamemnus and Mango can do exactly the same thing and beat me again...
Code:

WIDTH , 50: CLS
PRINT "PRIME CALCULATOR BY ANTONI GUAL agual@eic.ictnet.es"
INPUT "Maximum prime(1 to 1,000,000,000): "; mp&
CONST pp = 1024& * 16 - 1
CONST tabs = 10
CONST stor = 3400 'enough to calculate the 10,000,000 first primes
DIM pr(stor + 2) AS INTEGER
DIM pr1(stor + 2) AS LONG
DIM pr2(stor + 2) AS LONG
DIM ind AS LONG
pr(2) = 3
pr1(2) = 3
pr2(2) = 1
ind = 2
test& = 5
t! = TIMER
PRINT 2, 3,
CNT% = 2
DO
isprime% = -1
i% = 1
DO
i% = i% + 1
WHILE pr1(i%) < test&: pr1(i%) = pr1(i%) + pr(i%): pr2(i%) = pr2(i%) + 1: WEND
IF pr1(i%) = test& THEN isprime% = 0: EXIT DO
LOOP UNTIL pr2(i%) <= pr(i%)
IF isprime% THEN
ind = ind + 1
PRINT test&,
CNT% = CNT% + 1: IF CNT% = 250 THEN CLS : CNT% = 0
IF ind <= stor THEN
pr(ind) = test&
pr1(ind) = test& + test&
pr2(ind) = 2
END IF
END IF
test& = test& + 2
LOOP UNTIL (i% = stor) OR test& > mp& OR LEN(INKEY\$)

ERASE pr, pr1, pr2
PRINT : PRINT : PRINT "time for "; ind; "primes:"; TIMER - t!; ""
a\$ = INPUT\$(1)
 Logged

Antoni
toonski84
__/--\__

Posts: 2567

 « Reply #37 on: June 03, 2003, 03:04:03 PM »

hey!? where did my post go?

I left my computer on running your program last night dav... It went up and over 14,000,000 primes somehow.
 Logged

i]"I know what you're thinking. Did he fire six shots or only five? Well, to tell you the truth, in all this excitement, I've kinda lost track myself. But being as this is a .44 Magnum ... you've got to ask yourself one question: 'Do I feel lucky?' Well, do ya punk?"[/i] - Dirty Harry
Agamemnus
x/ \z

Posts: 3491

 « Reply #38 on: June 03, 2003, 03:10:05 PM »

I saw your post, with a New York Times window or something in the background. My post disappeared too.

"The case of the disappearing posts"!
 Logged

Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
toonski84
__/--\__

Posts: 2567

 « Reply #39 on: June 03, 2003, 03:16:54 PM »

I smell an admin behind this!!  Will Joe and Agamemnus find the masked post-deleter?  Can this madman be stopped??  Will Aunt Harriot stumble across our hero's secret identity??  Tune in tomorrow, same Bat-time, same Bat-channel!
 Logged

i]"I know what you're thinking. Did he fire six shots or only five? Well, to tell you the truth, in all this excitement, I've kinda lost track myself. But being as this is a .44 Magnum ... you've got to ask yourself one question: 'Do I feel lucky?' Well, do ya punk?"[/i] - Dirty Harry
ak00ma
Ancient Guru

Posts: 669

 « Reply #40 on: June 03, 2003, 04:04:40 PM »

The MATRIX gonna get you

 Logged

B 4 EVER
Touf
Member

Posts: 57

 « Reply #41 on: June 03, 2003, 04:18:50 PM »

Antoni , is this the program you mailed me ?

 Logged

have the simplest tastes of the World : I satisfy myself with the best !

http://ToufQb.free.fr
Antoni Gual
Na_th_an

Posts: 1434

 « Reply #42 on: June 03, 2003, 05:01:03 PM »

 Logged

Antoni
Agamemnus
x/ \z

Posts: 3491

 « Reply #43 on: June 03, 2003, 05:43:30 PM »

there is stuff missing in other sections, too!!!!

EDIT: Projects section.
 Logged

Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
whitetiger0990
__/--\__

Posts: 2964

 « Reply #44 on: June 03, 2003, 05:52:43 PM »

where?
 Logged

[size=10]Back by popular demand!
I will byte and nibble you bit by bit until nothing remains but crumbs.[/size]
 Pages: 1 2 [3] 4 5