Qbasicnews.com
December 08, 2019, 06:08:28 PM *
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 28799 times)
wizardlife
Na_th_an
*****
Posts: 1456


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

Antoni Gual
Na_th_an
*****
Posts: 1434



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

Antoni
Touf
Member
*
Posts: 57


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

 have the simplest tastes of the World : I satisfy myself with the best !

http://ToufQb.free.fr
Mango
Wandering Guru
***
Posts: 360



« Reply #18 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
Logged
Touf
Member
*
Posts: 57


WWW
« Reply #19 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 ?? :Huh:

lol
Logged

 have the simplest tastes of the World : I satisfy myself with the best !

http://ToufQb.free.fr
Agamemnus
x/ \z
*****
Posts: 3491



« Reply #20 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
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.
toonski84
__/--\__
*****
Posts: 2567



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

i]"I know what you're thinking. Did he fire six shots or only five? Well, to tell you the truth, in all this excitement, I've kinda lost track myself. But being as this is a .44 Magnum ... you've got to ask yourself one question: 'Do I feel lucky?' Well, do ya punk?"[/i] - Dirty Harry
Mango
Wandering Guru
***
Posts: 360



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



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

Antoni
Agamemnus
x/ \z
*****
Posts: 3491



« Reply #24 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...
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.
whitetiger0990
__/--\__
*****
Posts: 2964



WWW
« Reply #25 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
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 #26 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...
PRINT
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
Logged

Antoni
Agamemnus
x/ \z
*****
Posts: 3491



« Reply #27 on: June 02, 2003, 07:02:45 PM »

i'm lost.
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.
Mango
Wandering Guru
***
Posts: 360



« Reply #28 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!!! :-?
Logged
toonski84
__/--\__
*****
Posts: 2567



« Reply #29 on: June 02, 2003, 08:42:32 PM »

the world aint perfect....

hey, for pulling it out of me arse it worked okay, right?
Logged

i]"I know what you're thinking. Did he fire six shots or only five? Well, to tell you the truth, in all this excitement, I've kinda lost track myself. But being as this is a .44 Magnum ... you've got to ask yourself one question: 'Do I feel lucky?' Well, do ya punk?"[/i] - Dirty Harry
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!