Title: The PRIME NUMBERSPost by: Touf on May 04, 2003, 09:46:41 PM
Come and participate to this new challenge !
http://ToufQb.free.fr/Concours.php?langue=1 Well , let's see if you know your division and multiplication charts .... :D This is a NO TIME LIMIT contest ! Title: The PRIME NUMBERSPost by: toonski84 on May 04, 2003, 10:03:48 PM
this works well enough for me.
Code: INPUT number& FOR y& = 1 TO number& prime% = 0 FOR x& = 2 TO SQR(y&) - 1 IF y& / x& = y& \ x& THEN prime% = 1 NEXT x& IF prime% = 0 THEN PRINT y& NEXT y& Title: The PRIME NUMBERSPost by: Plasma on May 04, 2003, 10:09:48 PM
I emailed mine...
Title: The PRIME NUMBERSPost by: Touf on May 05, 2003, 09:54:21 AM
Please , send your programs by e-mail , then I'll be able to upload my website .
Thanx Title: The PRIME NUMBERSPost by: Touf on May 07, 2003, 12:23:12 AM
Nobody else to compete ?
Anyway , congratulations to Plasma357 for its very very fast program ! I couldn't believe it ! It's gonna be hard to do better ! Title: The PRIME NUMBERSPost by: Mango on May 07, 2003, 03:51:28 PM
Quote from: "Touf" Nobody else to compete ? Anyway , congratulations to Plasma357 for its very very fast program ! I couldn't believe it ! It's gonna be hard to do better ! This is what I usually use...it stores the small primes in an array then doesn't bother testing the suspect prime against nonprime factors. By changing lines that were commented out, you can make the program print every prime, output the primes to the file primes.dat, or print the most recent prime 1 time/sec. Code: DEFINT A-Z DIM smallprimes(1 TO 5000) AS INTEGER CLS a = 0 max = 3 maxsqur = max * max smallprimes(1) = 3 next1 = 5 count = 1 'OPEN "primes.dat" FOR BINARY AS 1 'vvvvvvvvvvvvvvvvvvvvvvvvvvvv'get little primes (first 3500) and put into an array--------------- DO WHILE count < 3500 DO a = a + 1 IF next1 MOD smallprimes(a) = 0 THEN GOTO notprime LOOP WHILE smallprimes(a) * smallprimes(a) < next1 count = count + 1 smallprimes(count) = next1 PRINT smallprimes(count); 'found a prime 'PUT 1, , next1 notprime: next1 = next1 + 2 a = 0 LOOP '^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ nextbig& = next1 - 2 CLS over: t& = TIMER 'vvvvvvvvvvvvvvvvvvvvvvvvvvvvv'get big primes DO DO a = a + 1 IF nextbig& MOD smallprimes(a) = 0 THEN GOTO notprime2 LOOP WHILE (nextbig& \ smallprimes(a)) > smallprimes(a) recent& = nextbig& 'found a prime 'PRINT nextbig&; 'PUT 1, , nextbig& notprime2: nextbig& = nextbig& + 2 a = 0 LOOP UNTIL TIMER - t& > 1 '^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ LOCATE 1 PRINT recent& GOTO over I thought this was a pretty fast way of getting them until I saw the program: Code: 'Prime Number Generator 'Algorithm from Knuth's "Sorting and Searching" Page 617 'Programmed by Rich Geldreich ' 'Notes: This prime number generator uses a disk file '"PRIMEBUF.BIN" to hold the prime numbers, so little RAM memory is 'needed. Each prime number is represented as the difference 'between the last prime number by a single byte. In other words, 'the gap between each prime number is stored instead of each prime 'number itself. All gaps are even numbers, because all primes 'must be odd numbers. Therefore, each byte can represent a gap of 'up to 510, because the least significant bit of each gap length 'is always unused. (Except for the special cases of 1-2, and 2-3. 'These primes aren't stored in the disk file; they're assumed to 'be present.) Since the maximum gap between all consecutive primes 'up to 436,273,009 is only 286, a single byte is good enough for 'this program!) ' 'The program stops when escape is pressed or when the priority 'queue is full. ' 'On a 286/10, roughly 3.2 million prime numbers were calculated in 'about 2.5 hours by this program. ' DEFINT A-Z DECLARE SUB PutPrime (a&) DECLARE FUNCTION GetPrime& () 'Maximum prime candidate = HeapSize*HeapSize CONST HeapSize = 4096 CONST IOSize = 2048 OPEN "primebuf.bin" FOR OUTPUT AS #1: CLOSE #1 OPEN "primebuf.bin" FOR BINARY AS #1 DIM SHARED PrimeBuf1 AS STRING * IOSize, Buf1Loc, Buf1FLoc AS LONG DIM SHARED PrimeBuf2 AS STRING * IOSize, Buf2Loc, Buf2FLoc AS LONG DIM SHARED SlideFlag DIM SHARED LastPrime1&, LastPrime2& Buf1Loc = 1 + (1 - 1): Buf1FLoc = 1 Buf2Loc = 1 + (2 - 1): Buf2FLoc = 1 LastPrime1& = 3 LastPrime2& = 5 'Priority queue DIM HeapQ(1 TO HeapSize) AS LONG DIM HeapQ1(1 TO HeapSize) AS LONG DIM HeapQ2(1 TO HeapSize) AS LONG DIM SHARED n AS LONG DIM t AS LONG DIM Q AS LONG, Q1 AS LONG, Q2 AS LONG DIM TQ AS LONG, TQ1 AS LONG DIM u AS LONG n = 5 d = 2 r = 1 t = 25 HeapQ(1) = 25 HeapQ1(1) = 10 HeapQ2(1) = 30 DO DO Q = HeapQ(1) Q1 = HeapQ1(1) Q2 = HeapQ2(1) TQ = Q + Q1 TQ1 = Q2 - Q1 '***Insert Heap(1) into priority queue i = 1 DO j = i * 2 IF j <= r THEN IF j < r THEN IF HeapQ(j) > HeapQ(j + 1) THEN j = j + 1 END IF END IF IF TQ > HeapQ(j) THEN HeapQ(i) = HeapQ(j) HeapQ1(i) = HeapQ1(j) HeapQ2(i) = HeapQ2(j) i = j ELSE EXIT DO END IF ELSE EXIT DO END IF LOOP HeapQ(i) = TQ HeapQ1(i) = TQ1 HeapQ2(i) = Q2 '*** LOOP UNTIL n <= Q DO WHILE n < Q PutPrime n n = n + d d = 6 - d LOOP IF n = t THEN u = GetPrime t = u * u '***Find location for new entry j = r + 1 DO i = j \ 2 IF i = 0 THEN EXIT DO END IF IF HeapQ(i) <= t THEN EXIT DO END IF HeapQ(j) = HeapQ(i) HeapQ1(j) = HeapQ1(i) HeapQ2(j) = HeapQ2(i) j = i LOOP '*** HeapQ(j) = t IF (u MOD 3) = 2 THEN HeapQ1(j) = 2 * u ELSE HeapQ1(j) = 4 * u END IF HeapQ2(j) = 6 * u r = r + 1 IF r = HeapSize THEN 'Don't overflow priority queue EXIT DO END IF END IF n = n + d d = 6 - d LOOP UNTIL LEN(INKEY$) 'Print prime numbers calculated. (Except for the last few 'which are still in the output buffer.) CLS SEEK #1, 1 LastPrime& = 3 PRINT 1; 2; 3; FOR a = 1 TO LOF(1) \ IOSize GET #1, , PrimeBuf1 FOR b = 1 TO IOSize LastPrime& = LastPrime& + ASC(MID$(PrimeBuf1, b, 1)) * 2 PRINT LastPrime&; NEXT IF LEN(INKEY$) THEN EXIT FOR NEXT CLOSE END FUNCTION GetPrime& IF SlideFlag = 0 THEN LastPrime2& = LastPrime2& + 2 * ASC(MID$(PrimeBuf1, Buf2Loc, 1)) ELSE LastPrime2& = LastPrime2& + 2 * ASC(MID$(PrimeBuf2, Buf2Loc, 1)) END IF GetPrime& = LastPrime2& Buf2Loc = Buf2Loc + 1 IF Buf2Loc = (IOSize + 1) THEN Buf2FLoc = Buf2FLoc + IOSize GET #1, Buf2FLoc, PrimeBuf2 Buf2Loc = 1 END IF END FUNCTION SUB PutPrime (a&) STATIC TotalPrimes AS LONG MID$(PrimeBuf1, Buf1Loc) = CHR$((a& - LastPrime1&) \ 2) Buf1Loc = Buf1Loc + 1 IF Buf1Loc = (IOSize + 1) THEN TotalPrimes = TotalPrimes + IOSize LOCATE , 1 PRINT "Primes found:"; TotalPrimes; "Maximum candidate:"; n; PUT #1, Buf1FLoc, PrimeBuf1 Buf1Loc = 1 Buf1FLoc = Buf1FLoc + IOSize IF SlideFlag = 0 THEN SlideFlag = -1 PrimeBuf2 = PrimeBuf1 END IF END IF LastPrime1& = a& END SUB Now this one is what I call fast!!! Title: The PRIME NUMBERSPost by: ak00ma on May 07, 2003, 05:25:38 PM
Code: DIM prime%(32000) FOR n% = 3 TO SQR(32000) STEP 2 FOR nn%= i * i TO 32000 STEP 2 * i prime%(nn%) = 1 NEXT nn% NEXT n% FOR n% = 3 TO 32000 STEP 2 IF prime%(n%) = 0 THEN PRINT n% NEXT n% Title: The PRIME NUMBERSPost by: RST on May 07, 2003, 05:34:21 PM
Just a quick question....
Does the program have to find *all* primes, or *just* primes? Obviously, programs will go a lot faster if it's just the second one. Title: The PRIME NUMBERSPost by: DrV on May 07, 2003, 09:52:26 PM
Hehe... obvious answer is "no" because there are theroretically infinite number of prime numbers... unless you mean within the range of a long int or something.
Title: The PRIME NUMBERSPost by: Agamemnus on May 08, 2003, 12:04:50 AM
Yeah... there is an infinite number of primes.
But is there an infinite number of double primes (3 5, 11 13, 17 19, 101 103)? Title: The PRIME NUMBERSPost by: RST on May 08, 2003, 11:12:37 AM
A word of clarrification....
I meant is it OK if the program skips a prime? For example, there's a few well-known algorithms that generate prime numbers, but they skip most of them. (eg: 3, 5, 11, 13.... [Skips 7]) I should point out that these algorthims are considerably faster than others.Title: The PRIME NUMBERSPost by: Touf on May 08, 2003, 02:22:39 PM
Am i dreaming ???
Of course ALL prime numbers have to be found ! If any prime number is forgotten , the program won't be accepted ! But please , mail me your programs , don't show it ... Title: The PRIME NUMBERSPost by: Touf on May 12, 2003, 09:47:25 AM
Short message for Mango ....
Can you please send me your e-mail and some informations about you ( see http://ToufQb.free.fr/classement.php?langue=1 ) Of course , if you don't want , don't do it :wink: Title: The PRIME NUMBERSPost by: Mango on May 12, 2003, 11:53:48 AM
Quote from: "Touf" Short message for Mango .... Touf, I'll be glad to send info...however, I wanted to make sure you were giving credit where it is due. The 1st program I listed is my own method...the second was conceptualized and programmed by someone else... It is unclear from your web-site which program was used. Also...to be fair to all the methods, they should be compiled, because interpreted qbasic slows down when comments are present, and for spaces between lines of code!!! Cheers Title: The PRIME NUMBERSPost by: Touf on May 12, 2003, 06:52:11 PM
lol
I've understood that your program was the first or the two ones ! But the program I'v tested is YOURS ... The other-one is REALLY the BEST , but I don't manage to make it stop at a specified number ... doesn't matter ... I've no info on this programmer . So , I won't class the second program . :wink: Title: The PRIME NUMBERSPost by: wizardlife on May 12, 2003, 07:11:35 PM
Quote from: "RST" A word of clarrification.... I meant is it OK if the program skips a prime? For example, there's a few well-known algorithms that generate prime numbers, but they skip most of them. (eg: 3, 5, 11, 13.... [Skips 7]) I should point out that these algorthims are considerably faster than others.Those break down after a point though... I read uh... some article on it once... yeah... Are there actually algos that consistently and accurately generate primes? Title: The PRIME NUMBERSPost by: Antoni Gual on May 13, 2003, 06:31:57 PM
It seems the only way to find all primes is to use the old Erathostenes's sieve. Even the second progam Mango posts is using it in a very convoluted way. The complication is to keep the primes stored in a file and only a sliding window on the sieve. The only goal of all this is to save memory, the sieve is still at the base.
This Rich Geldreich's code has been in the ABC packets since it's creation in 1995, but it mentions a 486 in the comments so I imagine the program has more than 10 years! I have tested it, it calculates all primes up to 2 000 000 in 6 seconds, then it needs 50 seconds to display them.. Title: The PRIME NUMBERSPost by: Touf on May 28, 2003, 09:46:05 PM
So , Mango ?
Can I have some informations about you ? ... because NOBODY has reach your level for the moment ! ( City , mail , URL ( if u have one ) ) .. you can send me these informations by mail if you want . Title: The PRIME NUMBERSPost by: Mango on May 29, 2003, 02:16:43 PM
Quote from: "Touf" NOBODY has reach your level for the moment !/quote] I just looked at the code I wrote earlier...and tweaked it a bit. This one is about 75% faster. The difference is I moved a squareroot out of a loop, and I got rid of a comparison and a goto. Code: DEFINT A-Z 'Joe Campbell-2003 DIM smallprimes(1 TO 3500) AS INTEGER 'array holds forst 3500 prime numbers CLS PRINT "This program finds primes, then prints the highest found, 1 per second" a = 0 max = 3 smallprimes(1) = 3 next1 = 5 count = 1 DO WHILE count < 3500 sqroot = SQR(next1) DO a = a + 1 IF next1 MOD smallprimes(a) = 0 THEN GOTO notprime LOOP WHILE sqroot > smallprimes(a) count = count + 1 smallprimes(count) = next1 notprime: next1 = next1 + 2 a = 0 LOOP nextbig& = next1 - 2 over: t& = TIMER t1& = t& + 1 DO sqroot = SQR(nextbig&) DO a = a + 1 IF sqroot < smallprimes(a) THEN APrime& = nextbig& EXIT DO END IF LOOP WHILE nextbig& MOD smallprimes(a) nextbig& = nextbig& + 2 a = 0 LOOP UNTIL TIMER > t1& LOCATE 2 PRINT APrime& GOTO over Title: The PRIME NUMBERSPost by: Touf on June 02, 2003, 08:31:41 AM
haha !
A french programer has send a faster program ! Are the French programers better than US programers ?? :???: lol Title: And the Russians beat the French.Post by: Agamemnus on June 02, 2003, 03:34:21 PM
Code: CLS 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% 4 IF i% = 32767 THEN GOTO 5 i% = i% + 2 GOTO 1 5 i2& = prime(cur.prime.amount%) i2& = i2& + 2 biggest.prime& = i2& i3# = TIMER + 1 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 biggest.prime& = i2& 9 i2& = i2& + 2 IF TIMER > i3# THEN i3# = TIMER + 1: PRINT biggest.prime& GOTO 6 'IF INKEY$ = "" THEN GOTO 6 Title: The PRIME NUMBERSPost by: toonski84 on June 02, 2003, 03:39:56 PM
Well, i've always thought french kissing is better than regular kissing, so the possibility's certainly there... But then again, American cheese kicks ass, what with Wisconsin and all so I can't really say now.
Title: Re: And the Russians beat the French.Post by: Mango on June 02, 2003, 05:09:03 PM
Nice job Agamemnus!!
I learned a bunch from your optimization of my code...Here's what I see from a quick look goto faster than do:loop putting an array element into a variable then calling that variable is faster than calling the array element repetedly a^.5 is faster than squ(a) any others that I missed? Thanks again for the optimization. Title: The PRIME NUMBERSPost by: Antoni Gual on June 02, 2003, 05:44:18 PM
Agamemnus: You should review your code, some of the numbers printed end in 5 so they can't be primes...
Title: The PRIME NUMBERSPost by: Agamemnus on June 02, 2003, 05:49:41 PM
Actually, SQR(x) is 2x faster than ^.5. I think that's because ^x uses a general method, and SQR(x) is a streamlined version of ^x, with a lot of things canceling out.
Your code is slower because: 1) You have a while loop for your timer 2) You use UNTIL instead of direct IFs... Of course a good compiler will make ^.5 into SQR(x). But qb45.exe isn't actually that smart.. EDIT: You're right, I fouled up. EDIT: Fixed... Title: The PRIME NUMBERSPost by: whitetiger0990 on June 02, 2003, 05:56:59 PM
I like my program that finds primes up to the number specified
Code: CLS INPUT n FOR i = 1 TO n a = i * 6 - 1 b = i * 6 + 1 IF a <= n THEN z = 1 DO z = z + 1 IF z = a THEN PRINT a: EXIT DO IF a / z = INT(a / z) THEN EXIT DO LOOP END IF IF b <= n THEN z = 1 DO z = z + 1 IF z = b THEN PRINT b: EXIT DO IF b / z = INT(b / z) THEN EXIT DO LOOP END IF NEXT Title: The PRIME NUMBERSPost by: Antoni Gual on June 02, 2003, 06:47:53 PM
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. Code: CLS PRINT "PRIME CALCULATOR BY ANTONI GUAL" 'indicate in stor how many primes you want CONST stor = 16383 'That's the maximum;you may have to set the /ah switch REDIM pr(stor) AS LONG REDIM pr1(stor) AS LONG REDIM pr2(stor) 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 2 and test our first candidate, 3 pr(0) = 2 pr1(0) = 2 pr2(0) = 1 maxx& = 2 ind% = 0 test& = 3 t! = TIMER DO isprime% = -1 FOR i% = 0 TO ind% WHILE pr1(i%) < test&: pr1(i%) = pr1(i%) + pr(i%): pr2(i%) = pr2(i%) + 1: WEND IF pr2(i%) <= pr(i%) THEN EXIT FOR IF pr1(i%) = test& THEN isprime% = 0: EXIT FOR NEXT IF isprime% THEN ind% = ind% + 1 IF (ind% AND 1023) = 0 THEN PRINT ind%; "th prime is:"; test& pr(ind%) = test& pr1(ind%) = test& pr2(ind%) = 1 END IF test& = test& + 1 LOOP UNTIL ind% = stor 'That's all! t1! = TIMER - t! PRINT : PRINT stor + 1; " primes found in"; t1!; " seconds."; : INPUT "Want to print them all? (Y/N)"; a$ IF UCASE$(a$) <> "Y" THEN END t! = TIMER 'array full, print it... FOR i% = 0 TO stor PRINT pr(i%), NEXT PRINT : PRINT stor + 1; " primes printed in "; TIMER - t!; "Not so fast..." ERASE pr, pr1, pr2 Title: The PRIME NUMBERSPost by: Agamemnus on June 02, 2003, 07:02:45 PM
i'm lost.
Title: ToonskiPost by: Mango on June 02, 2003, 08:32:55 PM
Quote from: "toonski84" this works well enough for me. Code: INPUT number& FOR y& = 1 TO number& prime% = 0 FOR x& = 2 TO SQR(y&) - 1 IF y& / x& = y& \ x& THEN prime% = 1 NEXT x& IF prime% = 0 THEN PRINT y& NEXT y& I hope you don't think I picking on you...your code pegs 25, 49, and 121 as prime...all have prime roots, but they themselves are not prime...I hope this isn't good enough for you!!! :-? Title: The PRIME NUMBERSPost by: toonski84 on June 02, 2003, 08:42:32 PM
the world aint perfect....
hey, for pulling it out of me arse it worked okay, right? Title: The PRIME NUMBERSPost by: Antoni Gual 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 :D, 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 Title: Antonio...re not using squareroots...Post by: Mango 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. Title: The PRIME NUMBERSPost by: Antoni Gual 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 "Total time "; TIMER - t!; "seconds. Results are in the file PRIMES.TXT" Title: The PRIME NUMBERSPost by: Touf on June 03, 2003, 06:07:14 AM
okay !
I'll chek your programs ( Antoni and Agamemnus ) , and I'll update the classification soon . Title: The PRIME NUMBERSPost by: Touf 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 ? Title: WHAT! WheRE DID MY POST GO?Post by: Agamemnus 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. Title: The PRIME NUMBERSPost by: Antoni Gual 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) Title: The PRIME NUMBERSPost by: toonski84 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. Title: The PRIME NUMBERSPost by: Agamemnus 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"! :o Title: The PRIME NUMBERSPost by: toonski84 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!Title: The PRIME NUMBERSPost by: ak00ma on June 03, 2003, 04:04:40 PM
The MATRIX gonna get you8) Title: The PRIME NUMBERSPost by: Touf on June 03, 2003, 04:18:50 PM
Antoni , is this the program you mailed me ?
If not , mail me your last version please ! Title: The PRIME NUMBERSPost by: Antoni Gual on June 03, 2003, 05:01:03 PM
Touf: Check your e-mail
Title: The PRIME NUMBERSPost by: Agamemnus on June 03, 2003, 05:43:30 PM
there is stuff missing in other sections, too!!!!
EDIT: Projects section. Title: The PRIME NUMBERSPost by: whitetiger0990 on June 03, 2003, 05:52:43 PM
where?
Title: The PRIME NUMBERSPost by: Neo on June 04, 2003, 06:42:01 AM
Quote from: "toonski84" I left my computer on running your program last night dav... It went up and over 14,000,000 primes somehow. Whow! 14,000,000! Not bad :) Mine got till the LONG overflow, that is up to and including 7FFFh ;) And just in 1,5 hour Title: The PRIME NUMBERSPost by: Mango on June 04, 2003, 11:48:17 AM
Quote from: "Neo" Mine got till the LONG overflow, that is up to and including 7FFFh ;) And just in 1,5 hour That's pretty good. What's your method? I just compiled a slightly modified version (doesn't poll the timer, instead prints a prime every 64 k found) of mine and it's running in a background window on a 1.5 GHz machine...it's been on for a whopping 7 min 20 sec and the most recent prime is 19,562,177...at this rate, mine's not set to overflow the long integer until about 13 hrs. I'd like to see your method...it kicks my methods ass. Is it a method that picks primes with high probability, or does it exhastively prove each prime? Anyway...we're up to 11 min, 30 sec and latest prime is.... 27,033,163... edits: 36 min...60,193,877 3 h 41 min...240,677,251 Title: The PRIME NUMBERSPost by: Antoni Gual on June 04, 2003, 08:13:46 PM
Mango:
First of all your method is faster than your results. You should leave the computer runing your compiled program alone in the foreground. This way you should reach the long overflow before 4 hours. And the 1,5 hour could be reached by the program by Rich Geldreich you posted when this challenge started (you said clearly you did'nt write it). I have no patience to check it but it could reach the limits in 1,5 hour as Neo says. Remember i'ts a program ported from the computer bible "The Art of Computer Programming" so it should be good. By the way , could someone explain me how does it work? Edited: About speed, don't forget there are AMD processors abe to run 16 bits apps 3 times faster than a P4 1,5...Any speed comparison should be done in the same computer! Title: The PRIME NUMBERSPost by: Agamemnus on June 04, 2003, 08:19:03 PM
It checks every odd number for primality by seeing if it is evenly divisible by every number that is less than 32767.
The reason is that it is slower to do mod using integers, but you can only check up to 32761 (I think it's a prime) squared. A number can be checked for primality by just doing mod all primes less than the square root of that number because you just check the same numbers over again after... (x+1)(x-1) (x-1)(x+1) Title: The PRIME NUMBERSPost by: Neo on June 05, 2003, 04:12:11 AM
Quote from: "Mango" Quote from: "Neo" Mine got till the LONG overflow, that is up to and including 7FFFh ;) And just in 1,5 hour That's pretty good. What's your method? I just compiled a slightly modified version (doesn't poll the timer, instead prints a prime every 64 k found) of mine and it's running in a background window on a 1.5 GHz machine...it's been on for a whopping 7 min 20 sec and the most recent prime is 19,562,177...at this rate, mine's not set to overflow the long integer until about 13 hrs. I'd like to see your method...it kicks my methods ass. Is it a method that picks primes with high probability, or does it exhastively prove each prime? Anyway...we're up to 11 min, 30 sec and latest prime is.... 27,033,163... edits: 36 min...60,193,877 3 h 41 min...240,677,251 It wasn't made in QB :). However, these are the test results with my program made in QB: 1 min: 2,000,000 2 min: 4,031,482 1 h: 240,482,843 The programming algorithm was the Sea of Erathetos. However, there are much faster algorithms :) Title: The PRIME NUMBERSPost by: Antoni Gual on June 06, 2003, 11:01:24 AM
This one is a 30% faster than my former post
Code: WIDTH , 50: CLS PRINT "PRIME CALCULATOR BY ANTONI GUAL agual@eic.ictnet.es" INPUT "Maximum prime(5 to 2,100,000,000): "; mp& CONST stor = 3400 'enough to calculate the 5,000,000 first primes DIM pr(stor) AS LONG 'keeps 2 * prime (the increment to next multiple) DIM pr1(stor) AS LONG 'keeps the current muliple of the prime 'seed the tables pr(2) = 2 * 3 pr1(2) = 3 * 3 'init vars ind& = 2 ind2% = 2 sqre& = 5 * 5 'first prime tested test& = 5 'just a trick to avoid W2000 to lower priority OPEN "nul" FOR OUTPUT AS #1 t! = TIMER PRINT 2, 3, CNT% = 2 DO i% = 1 DO i% = i% + 1 WHILE pr1(i%) < test&: pr1(i%) = pr1(i%) + pr(i%): WEND IF pr1(i%) = test& THEN GOTO noprime LOOP UNTIL i% = ind2% 'it's a prime, print it ind& = ind& + 1 PRINT test&, 'scroll screen if needed (And keep priority high in W2000) CNT% = CNT% + 1: IF CNT% = 250 THEN CLS : CNT% = 0: PRINT #1, "."; 'add to primes table IF ind& <= stor THEN : pr(ind&) = test&: IF ind2% = stor THEN EXIT DO noprime: 'go for next prime test& = test& + 2 'if beyond square of last divisor, add a new divisor to tests IF test& > sqre& THEN ind2% = ind2% + 1: sqre& = pr(ind2%) * pr(ind2%) pr1(ind2%) = sqre& pr(ind2%) = pr(ind2%) + pr(ind2%) IF LEN(INKEY$) THEN EXIT DO END IF LOOP UNTIL test& > mp& ''STOP ERASE pr, pr1 PRINT : PRINT : PRINT "time for "; ind&; "primes: "; TIMER - t!; "seconds" a$ = INPUT$(1) I'm now figuring out how to sort my arrays, it should be even faster Title: The PRIME NUMBERSPost by: Joakim on June 07, 2003, 06:21:16 PM
This one is really neat. It's fast and it's small.
Code: FOR i& = 0 to 2147483647 PRINT i& NEXT Now, don't tell me it doesn't print out all the prime numers :P Title: The PRIME NUMBERSPost by: Agamemnus on June 07, 2003, 08:25:25 PM
LOOPHOLE!
Title: The PRIME NUMBERSPost by: Antoni Gual on June 08, 2003, 10:20:23 AM
I should have had that idea...
Title: The PRIME NUMBERSPost by: whitetiger0990 on June 08, 2003, 08:34:57 PM
This finds primes. But slowly. Antoni Gual i need to look at your prog to find an easier way to tell of a number isn't prime.
Code: CLS WIDTH , 50 INPUT pm t = TIMER FOR p = 3 TO pm STEP 2 FOR i = 2 TO p - 1 IF p / i = INT(p / i) THEN np = 1: EXIT FOR NEXT i IF np = 1 THEN np = 0 ELSE r = r + 1: PRINT p, : r2 = r2 + 1 IF r2 = 5 THEN r2 = 0: r = r + 1: IF r = 250 THEN r = 0: CLS NEXT p PRINT : PRINT : PRINT USING "####.##"; TIMER - t Title: The PRIME NUMBERSPost by: Antoni Gual on June 08, 2003, 09:01:28 PM
This is the faster I can do. It uses a priority queue to keep the multiples array ordered. I learned about this useful construction by participating there, so I thank you all for that.:D
Code: WIDTH , 50: CLS CONST maxlng = &H7FFFFFFF PRINT "PRIME CALCULATOR BY ANTONI GUAL agual@eic.ictnet.es" DO PRINT "Maximum prime(5 to "; maxlng; "): "; : INPUT mp& LOOP UNTIL mp& >= 5 AND mp& <= maxlng CONST stor = 4750 DIM pr(stor + 1) AS LONG DIM pr1(stor + 1) AS LONG pr(1) = 2 * 3 pr1(1) = 3 * 3 ind& = 1 ind2% = 1 pr1(2) = maxlng sqre& = 3 * 3 test& = 5 OPEN "nul" FOR OUTPUT AS #1 t! = TIMER PRINT 2, 3, CNT% = 2 DO DO a& = pr1(1) IF a& >= test& THEN EXIT DO b& = pr(1) a& = a& + b& i% = 1 DO j% = i% + i% IF j% > ind2% THEN EXIT DO IF pr1(j%) > pr1(j% + 1) THEN j% = j% + 1 IF a& <= pr1(j%) THEN EXIT DO pr(i%) = pr(j%) pr1(i%) = pr1(j%) i% = j% LOOP pr1(i%) = a& pr(i%) = b& LOOP IF a& > test& THEN ind& = ind& + 1 PRINT test&, 'the print #1 "." is just for W2000, you can erase it if you want CNT% = CNT% + 1: IF CNT% = 250 THEN CLS : CNT% = 0: PRINT #1, "."; IF ind& <= stor THEN pr(ind&) = test&: IF ind2% = stor THEN EXIT DO END IF test& = test& + 2 IF test& > sqre& THEN GOSUB addnew IF LEN(INKEY$) THEN EXIT DO END IF LOOP UNTIL test& > mp& PRINT : PRINT : PRINT "time for "; ind& + 1; "primes: "; TIMER - t!; "seconds" a$ = INPUT$(1) END addnew: ind2% = ind2% + 1 a& = pr(ind2%) sqre& = a& * a& j% = ind2% DO i% = j% \ 2 IF i% = 0 THEN EXIT DO IF pr1(i%) <= sqre& THEN EXIT DO pr(j%) = pr1(i%) pr1(j%) = pr1(i%) j% = i% LOOP pr1(j%) = sqre& pr(j%) = a& + a& pr1(j% + 1) = maxlng RETURN The person that started this, Touf seems to have vanished in the air, his contest site has not been updated in a week. So who's the judge?.... Title: The PRIME NUMBERSPost by: oracle on June 08, 2003, 09:12:21 PM
Hmmm, I do have a question. Is it possible to make a prime searching routine that checks numbers in strings, like those produced by BIGINT, BIGNUM (and StatLib when it arrives)? You know, numbers larger than can normally be handled by the traditional data types, 2000!-1 for example.
Title: The PRIME NUMBERSPost by: Antoni Gual on June 08, 2003, 09:45:05 PM
Oracle:
This is a different problem than finding all primes up to a number. AFAIK, to check if a number is prime you must check if it's divisible by some prime from 2 to the suare root of the number. It means if your number is 2^62 you must have all the primes from 2 to 2^31 in a table. There are aproximately 100 million primes in that range. You coud calculate them previously and save them in a table. Rich Geldreich's progam generates in 1 hour such a table and stores it in a compressed format, 1 byte per prime but be aware the table is 100 Meg in size... A less bloated approach would be to divide by every number from 2 to square root of n, it would work but it would be very inefficient. Title: The PRIME NUMBERSPost by: oracle on June 08, 2003, 09:46:37 PM
It was just an idea for StatLib, maybe I'll add such a searcher in a later version, I can't be bothered coding such a thing now.
Title: The PRIME NUMBERSPost by: Agamemnus on June 08, 2003, 10:59:30 PM
No, to check if a number is prime, you do NOT have to check from 2 to that number ^ .5. google.com: "primes", first entry.
Title: The PRIME NUMBERSPost by: whitetiger0990 on June 08, 2003, 11:24:39 PM
Code: CLS WIDTH , 50 p = 3 t = TIMER DO FOR i = 2 TO SQR(p) IF p / i = INT(p / i) THEN np = 1: EXIT FOR NEXT i IF np = 1 THEN np = 0 ELSE IF c = 1 THEN c = 0: PRINT USING "Time: ####.##"; TIMER - t: PRINT : LOCATE 1, 1 PRINT p, c = c + 1 pn = pn + 1 END IF p = p + 2 LOOP UNTIL LEN(INKEY$) = 1 PRINT pn; " primes found" PRINT USING "In ####.## sec"; TIMER - t Antoni Gual: I was testing both of ours on primes up to 100000 Antoni Gual: 1 sec, found 9593 primes Mine: 8 sec, found 9591 primes one of ours is messed up. and im gussing it's mine. Title: The PRIME NUMBERSPost by: Agamemnus on June 08, 2003, 11:30:34 PM
You didn't store anything. He did.
Title: The PRIME NUMBERSPost by: whitetiger0990 on June 08, 2003, 11:36:36 PM
So you saying that i forgot two primes? or did he happen to find two just laying on the ground.
Title: The PRIME NUMBERSPost by: Agamemnus on June 09, 2003, 03:07:18 PM
Well, you didn't count the first prime (2) and the last one, probably.
I was talking about actually going through primes, not every number, like you did..... the reason why yours is slower. Title: The PRIME NUMBERSPost by: Mango on June 09, 2003, 03:39:05 PM
Quote from: "Joakim" This one is really neat. It's fast and it's small. Code: FOR i& = 0 to 2147483647 PRINT i& NEXT Now, don't tell me it doesn't print out all the prime numers :P That's pretty good...this one's more than twice as fast though!!! Code: PRINT "2"; FOR x& = 3 to 2147483647 STEP 2 PRINT x&; NEXT x& Title: The PRIME NUMBERSPost by: Antoni Gual on June 09, 2003, 03:53:39 PM
whitetiger:
The two programs, yours an mine are both not counting correctly the number of primes they display. You display 2 and don't count it. I don't display 1 (it can't be considered a prime, actually) but i count it. So there is the difference. Title: The PRIME NUMBERSPost by: whitetiger0990 on June 09, 2003, 04:55:54 PM
Code: CLS WIDTH , 50 p = 2 t = TIMER DO FOR i = 2 TO SQR(p) IF p = 2 THEN EXIT FOR IF p MOD i = 0 THEN np = 1: EXIT FOR NEXT i IF np = 1 THEN np = 0 ELSE 'IF c = 1 THEN c = 0: PRINT USING "Time: ####.##"; TIMER - t: PRINT : LOCATE 1, 1 PRINT p, : PRINT USING "Time: ####.##"; TIMER - t: PRINT : LOCATE 1, 1 'c = c + 1 pn = pn + 1 END IF IF p = 2 THEN p = 3 ELSE p = p + 2 LOOP UNTIL p >= 100000'LEN(INKEY$) = 1 PRINT pn; " primes found" PRINT USING "In ####.## sec"; TIMER - t Print and counts number 2 Title: The PRIME NUMBERSPost by: oracle on June 09, 2003, 10:11:27 PM
antoni: just take one from your result then.
Title: The PRIME NUMBERSPost by: Antoni Gual on June 10, 2003, 07:01:10 PM
Yes, I should do it. I was just using a program that counts 1 as prime as speed reference while developing mine . I just forgot to modify it before posting.
Title: The PRIME NUMBERSPost by: Mango on June 13, 2003, 04:55:13 AM
Quote from: "Neo" Mine got till the LONG overflow, that is up to and including 7FFFh ;) And just in 1,5 hour It wasn't made in QB :). However, these are the test results with my program made in QB: 1 min: 2,000,000 2 min: 4,031,482 1 h: 240,482,843 Hey Neo...I'm fiddling with C the last couple days...here's a c port of my basic primer finder...on my 1.5 GHz after 6 min, the biggest prime was 190,976,059. This looks similar to what you reported re flipping the signed 4-byte int after 1.5 hr...Mine uses unsigned, so I get to go all the way to ffffffff, instead of cutting short at 7fffffff. Cheers. Code: #include <iostream> using namespace std; int main() { unsigned short inc = 1; unsigned long c; unsigned long x; unsigned long stop; unsigned long count=0; unsigned long hold=1; unsigned short array[6540]={3}; cout << "Find primes up to what number? (4,200,000,000 max)\n"; cin >> stop; for (x=3; x<65536;x += 2) //get small primes, put in array { for (c=0; (x % array[c]) && (array[c]*array[c] < x) ; c++); if (x % array[c]) { //cout << x << " "; //use this line to show all primes array[inc++]=x; } } for (x=65537; x<stop;x += 2) //find large primes { for (c=0; (x % array[c]) && (array[c]*array[c] < x) ; c++); if (x % array[c]) { //cout << x << " "; //use this line to show all primes if (count++ > hold) { cout << x << " "; //print every 100000th prime hold += 100000; } } } cout << "\n done\n"; return 0; } |