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
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
I should have had that idea...
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
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.
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?....
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.
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.
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.
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.