Qbasicnews.com
December 09, 2019, 07:10:28 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 ... 5
  Print  
Author Topic: The PRIME NUMBERS  (Read 28807 times)
Touf
Member
*
Posts: 57


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

This is a NO TIME LIMIT contest !
Logged

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

http://ToufQb.free.fr
toonski84
__/--\__
*****
Posts: 2567



« Reply #1 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&
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
Plasma
Na_th_an
*****
Posts: 1770


WWW
« Reply #2 on: May 04, 2003, 10:09:48 PM »

I emailed mine...
Logged
Touf
Member
*
Posts: 57


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

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

http://ToufQb.free.fr
Touf
Member
*
Posts: 57


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

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

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



« Reply #5 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!!!
Logged
ak00ma
Ancient Guru
****
Posts: 669



« Reply #6 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%
Logged

B 4 EVER
RST
Wandering Guru
***
Posts: 326



« Reply #7 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.
Logged
DrV
Na_th_an
*****
Posts: 1553



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



« Reply #9 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)?
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.
RST
Wandering Guru
***
Posts: 326



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


WWW
« Reply #11 on: May 08, 2003, 02:22:39 PM »

Am i dreaming Huh

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

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

http://ToufQb.free.fr
Touf
Member
*
Posts: 57


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

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

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



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


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

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

http://ToufQb.free.fr
Pages: [1] 2 3 ... 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!