Neo


« Reply #45 on: June 04, 2003, 06:42:01 AM » 

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



Logged




Mango
Wandering Guru
Posts: 360


« Reply #46 on: June 04, 2003, 11:48:17 AM » 

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



Logged




Antoni Gual


« Reply #47 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!



Logged

Antoni



Agamemnus


« Reply #48 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)(x1) (x1)(x+1)



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.



Neo


« Reply #49 on: June 05, 2003, 04:12:11 AM » 

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



Logged




Antoni Gual


« Reply #50 on: June 06, 2003, 11:01:24 AM » 

This one is a 30% faster than my former post 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



Logged

Antoni



Joakim


« Reply #51 on: June 07, 2003, 06:21:16 PM » 

This one is really neat. It's fast and it's small. FOR i& = 0 to 2147483647 PRINT i& NEXT
Now, don't tell me it doesn't print out all the prime numers



Logged




Agamemnus


« Reply #52 on: June 07, 2003, 08:25:25 PM » 

LOOPHOLE!



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


« Reply #53 on: June 08, 2003, 10:20:23 AM » 

I should have had that idea...



Logged

Antoni



whitetiger0990


« Reply #54 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. 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



Logged

[size=10]Back by popular demand! I will byte and nibble you bit by bit until nothing remains but crumbs.[/size]



Antoni Gual


« Reply #55 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. 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?....



Logged

Antoni



oracle


« Reply #56 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.



Logged




Antoni Gual


« Reply #57 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.



Logged

Antoni



oracle


« Reply #58 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.



Logged




Agamemnus


« Reply #59 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.



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.



