Qbasicnews.com
December 15, 2019, 10:15:07 AM *
Welcome, Guest. Please login or register.

Login with username, password and session length
News: Back to Qbasicnews.com | QB Online Help | FAQ | Chat | All Basic Code | QB Knowledge Base
 
   Home   Help Search Login Register  
Pages: 1 2 3 [4] 5
  Print  
Author Topic: The PRIME NUMBERS  (Read 28838 times)
Neo
Na_th_an
*****
Posts: 2150



« Reply #45 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 Smiley

Mine got till the LONG overflow, that is up to and including 7FFFh Wink
And just in 1,5 hour
Logged
Mango
Wandering Guru
***
Posts: 360



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

Quote from: "Neo"
Mine got till the LONG overflow, that is up to and including 7FFFh Wink
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
Na_th_an
*****
Posts: 1434



WWW
« 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
x/ \z
*****
Posts: 3491



« 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)(x-1)
(x-1)(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
Na_th_an
*****
Posts: 2150



« Reply #49 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 Wink
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 Smiley. 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 Smiley
Logged
Antoni Gual
Na_th_an
*****
Posts: 1434



WWW
« Reply #50 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
Logged

Antoni
Joakim
Senior Member
**
Posts: 230



WWW
« Reply #51 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  Tongue
Logged
Agamemnus
x/ \z
*****
Posts: 3491



« 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
Na_th_an
*****
Posts: 1434



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

I should have had that idea...
Logged

Antoni
whitetiger0990
__/--\__
*****
Posts: 2964



WWW
« 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.

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
Logged


[size=10]Back by popular demand!
I will byte and nibble you bit by bit until nothing remains but crumbs.[/size]
Antoni Gual
Na_th_an
*****
Posts: 1434



WWW
« 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.Cheesy

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?....
Logged

Antoni
oracle
*/-\*
*****
Posts: 3652



WWW
« 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
Na_th_an
*****
Posts: 1434



WWW
« 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
*/-\*
*****
Posts: 3652



WWW
« 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
x/ \z
*****
Posts: 3491



« 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.
Pages: 1 2 3 [4] 5
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.21 | SMF © 2015, Simple Machines Valid XHTML 1.0! Valid CSS!