Qbasicnews.com

Pages: 1 2 3 4 5 6 7

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 Big Grin

, 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

Quote: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.

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"

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

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 ?

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.

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)

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.

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

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!

Pages: 1 2 3 4 5 6 7

Antoni Gual

Mango

Antoni Gual

Touf

Touf

Agamemnus

Antoni Gual

toonski84

Agamemnus

toonski84