The PRIME NUMBERS

[Antoni Gual]

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

[Mango]

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.

[Antoni Gual]

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"

[Touf]

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

[Touf]

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 ?

[Agamemnus]

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.

[Antoni Gual]

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)

[toonski84]

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.

[Agamemnus]

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"! :o

[toonski84]

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!