View Full Version : A QBasic Program that calculates a range of prime numbers.

37818

12-20-2014, 05:33 PM

This program calculates a range of prime numbers:

PRINT "INPUT NUMBERS FOR A RANGE OF PRIMES"

INPUT "FIRST NUMBER: ", F#

INPUT "LAST NUMBER: ", L#

FOR A# = F# TO L#

IF (A# + 1) / 6 = INT((A# + 1) / 6) THEN GOTO LBL2

GOSUB LBL1

IF INKEY$ <> "" THEN SYSTEM

NEXT A#

PRINT

SYSTEM

LBL2:

F# = A#

FOR A# = F# TO L# STEP 6

GOSUB LBL1

IF INKEY$ <> "" THEN SYSTEM

A# = A# + 2

GOSUB LBL1

IF INKEY$ <> "" THEN SYSTEM

A# = A# - 2

NEXT A#

PRINT

SYSTEM

LBL1:

IF A# > 999999999999999# THEN PRINT "OUT OF RANGE": SYSTEM

IF A# < 1 OR A# <> INT(A#) THEN SYSTEM

IF A# = 2 OR A# = 3 THEN PRINT A#; : RETURN

C# = (A# + 1) / 6

IF C# = INT(C#) THEN GOSUB M

C# = (A# - 1) / 6

IF C# = INT(C#) THEN GOSUB P

RETURN

P:

FOR B# = 1 TO C#

A1# = (C# - B#) / (6 * B# + 1): A2# = (C# + B#) / (6 * B# - 1)

IF B# > A1# AND B# > A2# THEN PRINT A#; : RETURN

IF A1# = INT(A1#) OR A2# = INT(A2#) THEN RETURN

NEXT B#

RETURN

M:

FOR B# = 1 TO C#

A1# = (C# + B#) / (6 * B# + 1): A2# = (C# - B#) / (6 * B# - 1)

IF B# > A1# AND B# > A2# THEN PRINT A#; : RETURN

IF A1# = INT(A1#) OR A2# = INT(A2#) THEN RETURN

NEXT B#

RETURN

Leonhard

12-21-2014, 10:01 AM

Why all the QBASIC?

37818

12-22-2014, 08:43 AM

Why all the QBASIC?

A number of reasons. 1) I have been programming in BASIC 34 years. 2). That interpreter runs in a Windows OS. 3) It is both free to use and is readily available.

Leonhard

12-30-2014, 03:34 AM

A number of reasons. 1) I have been programming in BASIC 34 years. 2). That interpreter runs in a Windows OS. 3) It is both free to use and is readily available.

That's alright, though I really, really, really, recommend you pick up Python or C. As it is I do remember learning QBASIC as my first language. :smile:

Just glancing through the code there's a possible bug. You use doubles. I understand why you do so, but it comes with problems, especially when you get near the limit, where the rounding off trick you do won't work well. I suggest using Long (&) [up to 2147483647] or _INTEGER64 (&&) [up to 9223372036854775807]. The latter will provide more than enough for any prime ranges mortal computer can output.

I see you use a trick to check whether a number has a modulo remainer of zero.

(A# + 1) / 6 = INT((A# + 1) / 6)

Now A#, F# and L# are floats, but they will represent small integers fairly well and allow for the decimal fractions you want for that trick. However its a little bit ugly, and it will probably get you into trouble later when you get closer to the round-off errors, ...52345.0 + 1 might return ...52345.999... instead and so you'd evaluate true even when you shouldn't. The same error could occur during division as well.

So I suggest you use BASICS built-in way for calculating modulo remainders, and of course use Long Integers.

(A& + 1) MOD 6 = 0

This is much cleaner, should run just as well and be faster.

Leonhard

12-31-2014, 04:05 AM

999999999999999#

Given that this isn't a variable, does it even make sense to write the asterix at the end? I don't know enough about q64 to see if that would even run?

So far I haven't been able to get your code to run.

Leonhard

12-31-2014, 05:02 AM

Here's some python that accomplishes the same, albiet not with the same algorithm. Since I can't get your code to work 37818 I can't time it against yours. However, timing this using the unix time command gives me that it spent 3.2 seconds calculating all primes up to 1000000 and subsequently printing them. The majority of that time arguably spent printing them.

# Get User Input

print "Input numbers for a range of primes"

first = int(input("First Number: "))

last = int(input("Last Number: "))

# Calculate primes using simple Eratosthenes Sieve

p = [2] + range(3, last + 1);

n = 0

while (p[n]**2 <= last):

p = [i for i in p if (i == p[n]) or (i%p[n] != 0)]

n += 1

# Print all primes larger than first

while p:

if (p[0] >= first):

print p[0]

p.pop(0)

37818

12-31-2014, 08:36 PM

An Eratosthenes Sieve is by far the fastest way to obtain prime numbers.

Again my choice of Qbasic is because it is, for me, an easy high level programming language to use. Most programming as you know, is done with high level languages with better low level access to memory and cpu.

The 999999999999999# is the double precision number format in Qbasic.

Now the algorithm used in my program was chosen because it was that algorithm. Not that it was fast. It has too many operators/calculations.

That algorithm is based on two sets of numbers. 5 incremented by 6. And 7 incremented by 6. All the non-prime numbers in each set also can be factored by a number in the same set. The 5 set being the (number + 1) / 6 sets. And the 7 sets being the (number - 1) / 6 sets. Anyway that is part of what is behind the algorithm.

INPUT A#

IF A#>999999999999999 THEN PRINT "OUT OF RANGE":SYSTEM

IF A# <= 1 OR A# <> INT(A#) THEN SYSTEM

GOSUB S

IF A# = 2 OR A# = 3 THEN PRINT A#; "IS A PRIME NUMBER.": GOSUB S: SYSTEM

C# = (A# + 1) / 6

IF C# = INT(C#) THEN GOTO M

C# = (A# - 1) / 6

IF C# = INT(C#) THEN GOTO P

PRINT A#; "IS NOT A PRIME NUMBER.": GOSUB S: SYSTEM

P:

FOR B# = 1 TO C#

A1# = (C# - B#) / (6 * B# + 1): A2# = (C# + B#) / (6 * B# - 1)

IF B# > A1# AND B# > A2# THEN PRINT A#; "IS A PRIME NUMBER.": GOSUB S: SYSTEM

IF A1# = INT(A1#) OR A2# = INT(A2#) THEN PRINT A#; "IS NOT A PRIME NUMBER.": GOSUB S: SYSTEM

NEXT B#

M:

FOR B# = 1 TO C#

A1# = (C# + B#) / (6 * B# + 1): A2# = (C# - B#) / (6 * B# - 1)

IF B# > A1# AND B# > A2# THEN PRINT A#; "IS A PRIME NUMBER.": GOSUB S: SYSTEM

IF A1# = INT(A1#) OR A2# = INT(A2#) THEN PRINT A#; "IS NOT A PRIME NUMBER.": GOSUB S: SYSTEM

NEXT B#

S:

PRINT TIME$

RETURN

Now a faster increment by 6 and then 2 method:

INPUT N#

IF N# > 999999999999999# THEN PRINT "OUT OF RANGE": SYSTEM

GOSUB T

IF N# < 2 OR N# <> INT(N#) THEN GOSUB T: SYSTEM

IF N# / 2# = INT(N# / 2#) OR N# / 3# = INT(N# / 3#) THEN PRINT N#; "IS NOT A PRIME NUMBER.": GOSUB T: SYSTEM

C# = INT(SQR(N#))

FOR B# = 5# TO C# STEP 6#

IF N# / B# = INT(N# / B#) OR N# / (B# + 2#) = INT(N# / (B# + 2#)) THEN PRINT N#; "IS NOT A PRIME NUMBER.": GOSUB T: SYSTEM

NEXT B#

PRINT N#; "IS A PRIME NUMBER.": GOSUB T: SYSTEM

T:

PRINT TIME$

RETURN

This one should be easier to convert.

Leonhard

01-01-2015, 07:01 AM

An Eratosthenes Sieve is by far the fastest way to obtain prime numbers.

It can be varied a lot, even multithreaded. :smile:

Again my choice of Qbasic is because it is, for me, an easy high level programming language to use. Most programming as you know, is done with high level languages with better low level access to memory and cpu.

Its debatable how often high level languages are used, I find I'm using C far more often than python, then again I tend to write stuff where low-level access is a good thing. Though it depends on what you're developing.

QBASIC however is not a good language. It was meant as a simple educational tool, easy to learn. Its way, way outdated by now. Its hard to read, and it relies on gotos, basically, in order to perform the work of functions and subroutines.

It makes for spaghetti code.

And saying you're doing it because that's what's done in the business... do you code QBASIC for a company on a regular basis or is this a hobby thing? I kinda find the former hard to imagine.

Even if you're a hobby coder, seriously, learn Python. Its not hard, and you'll be learning real high-level programming concepts, like list comprehension, object oriented programming... What QBASIC offers is... low-level language, but interpreted like a high-level language. Which means it looks kinda like assembler, yet it performs worse than Python. About the only advantage I can see is that you don't have to worry about memory management (Java and Python have this though), you can dynamically declare variables (Python is even better at this). However you can't declare functions, there's only one global scope for the namespace, there's no cross platform compatibility (unlike Python right out of the bat).

The 999999999999999# is the double precision number format in Qbasic.

Alright, just couldn't get it to work in the interpreter I attempted to run.

Now the algorithm used in my program was chosen because it was that algorithm. Not that it was fast. It has too many operators/calculations.

In that case I think its better just to write the algorithm in pseudocode. You can test out an implementation of it in another language just fine, even QBASIC, but if you want others to look at your algorithm then that's what you'd do.

Though maybe you wanted feedback on your QBASIC implementation?

My criticism of using floats still stands. Please don't do that, you're setting yourself up for bugs! Its probably safe for the small integers you'll be calculating with this, but its really not a safe thing to do, and you're forced to use ugly hacks like "N# / 2# = INT(N# / 2#)" instead of the superior "N& MOD 2 = 0", which instantly makes sense to the eyes and is bugfree. My other concern is that you tend to use abstract labels which obscure the purpose of the code. LBL1 (Label 1), LBL2 (Label 2), P and M? I premuse these are set up simple to test primality of the numbers they get, but this could have been indicated in the names. The code is also uncommented, again, something that doesn't help with readability.

37818

01-01-2015, 08:43 AM

You are very correct, BASIC was intended for beginners. But permits what is deemed very poor unstructured programming habits. As you said, "Spaghetti code." Again, self descriptive variable names are easier to follow than simple single letter variables. [I have been programming using BASIC now over 30 some years. And some assembly language.]

37818

06-18-2016, 03:05 PM

A test program for factoring Mersenne numbers. Where 2prime - 1 = to a value. This test version can only do up to 259 - 1 = 179951 * 3203431780337

INPUT p#

IF p# = 2# OR p# = 3# THEN GOTO lbl

IF (p# - 1#) / 6# <> INT((p# - 1#) / 6#) AND (p# + 1#) / 6# <> INT((p# + 1#) / 6#) THEN PRINT p#; "is not prime.": SYSTEM

IF p# > 59# THEN PRINT "out of range.": SYSTEM

lbl:

x1# = -2#

x2# = -1#

x# = 0

m# = 2# ^ p# - 1#

c# = (m# - 1#) / (2# * p#)

IF p# = 2# THEN GOTO lbla

IF c# <> INT(c#) THEN PRINT p#; "is not prime.": SYSTEM

IF (p# - 5) / 6 = INT((p# - 5) / 6) THEN GOTO lbla

IF (p# - 7) / 6 = INT((p# - 7) / 6) THEN GOTO lblb

lbla:

x1# = x1# + 3#

x# = x# + 3#

y1# = (c# - x1#) / (2# * x1# * p# + 1#)

IF x1# > y1# THEN GOTO lblz

IF y1# = INT(y1#) THEN c# = y1#: GOSUB lblw: GOTO lbla

y# = (c# - x#) / (2# * x# * p# + 1#)

IF x# > y# THEN GOTO lblz

IF y# = INT(y#) THEN c# = y#: GOSUB lbly: GOTO lbla

IF y1# <> INT(y1#) AND y# <> INT(y#) THEN GOTO lbla

GOTO lbla

lblb:

x2# = x2# + 3#

x# = x# + 3#

y2# = (c# - x2#) / (2# * x2# * p# + 1#)

IF x2# > y2# THEN GOTO lblz

IF y2# = INT(y2#) THEN c# = y2#: GOSUB lblx: GOTO lblb

y# = (c# - x#) / (2# * x# * p# + 1#)

IF x# > y# THEN GOTO lblz

IF y# = INT(y#) THEN c# = y#: GOSUB lbly: GOTO lblb

IF y2# <> INT(y2#) AND y# <> INT(y#) THEN GOTO lblb

GOTO lblb

lblz:

PRINT (2# * c# * p# + 1#)

SYSTEM

lblw:

PRINT (2# * x1# * p# + 1#)

RETURN

lblx:

PRINT (2# * x2# * p# + 1#)

RETURN

lbly:

PRINT (2# * x# * p# + 1#)

RETURN

I only understood about 5% of this thread. :dizzy:

37818

06-18-2016, 07:13 PM

I only understood about 5% of this thread. :dizzy:OK.

From what you did understand. Ask a question where this discussion went off from what you did understand. Where you are interested of course.

OK.

From what you did understand. Ask a question where this discussion went off from what you did understand. Where you are interested of course.

No, no, I was just making a self-deprecating remark about my knowledge of computer science. Carry on.

37818

06-19-2016, 09:15 AM

No, no, I was just making a self-deprecating remark about my knowledge of computer science. Carry on.

Oh. I thought maybe you would like to discuss something regarding this. I know I left much unsaid.

37818

10-29-2017, 10:37 AM

A test program for factoring Mersenne numbers. Where 2prime - 1 = to a value. This test version can only do up to 259 - 1 = 179951 * 3203431780337

INPUT p#

IF p# = 2# OR p# = 3# THEN GOTO lbl

IF (p# - 1#) / 6# <> INT((p# - 1#) / 6#) AND (p# + 1#) / 6# <> INT((p# + 1#) / 6#) THEN PRINT p#; "is not prime.": SYSTEM

IF p# > 59# THEN PRINT "out of range.": SYSTEM

lbl:

x1# = -2#

x2# = -1#

x# = 0

m# = 2# ^ p# - 1#

c# = (m# - 1#) / (2# * p#)

IF p# = 2# THEN GOTO lbla

IF c# <> INT(c#) THEN PRINT p#; "is not prime.": SYSTEM

IF (p# - 5) / 6 = INT((p# - 5) / 6) THEN GOTO lbla

IF (p# - 7) / 6 = INT((p# - 7) / 6) THEN GOTO lblb

lbla:

x1# = x1# + 3#

x# = x# + 3#

y1# = (c# - x1#) / (2# * x1# * p# + 1#)

IF x1# > y1# THEN GOTO lblz

IF y1# = INT(y1#) THEN c# = y1#: GOSUB lblw: GOTO lbla

y# = (c# - x#) / (2# * x# * p# + 1#)

IF x# > y# THEN GOTO lblz

IF y# = INT(y#) THEN c# = y#: GOSUB lbly: GOTO lbla

IF y1# <> INT(y1#) AND y# <> INT(y#) THEN GOTO lbla

GOTO lbla

lblb:

x2# = x2# + 3#

x# = x# + 3#

y2# = (c# - x2#) / (2# * x2# * p# + 1#)

IF x2# > y2# THEN GOTO lblz

IF y2# = INT(y2#) THEN c# = y2#: GOSUB lblx: GOTO lblb

y# = (c# - x#) / (2# * x# * p# + 1#)

IF x# > y# THEN GOTO lblz

IF y# = INT(y#) THEN c# = y#: GOSUB lbly: GOTO lblb

IF y2# <> INT(y2#) AND y# <> INT(y#) THEN GOTO lblb

GOTO lblb

lblz:

PRINT (2# * c# * p# + 1#)

SYSTEM

lblw:

PRINT (2# * x1# * p# + 1#)

RETURN

lblx:

PRINT (2# * x2# * p# + 1#)

RETURN

lbly:

PRINT (2# * x# * p# + 1#)

RETURN

Here is an improved edit:

INPUT p#

IF p# = 2# OR p# = 3# THEN GOTO lbl

IF (p# - 1#) / 6# <> INT((p# - 1#) / 6#) AND (p# + 1#) / 6# <> INT((p# + 1#) / 6#) THEN PRINT p#; "is not prime.": SYSTEM

IF p# > 59# THEN PRINT "out of range.": SYSTEM

lbl:

x# = 0

k# = 0

m# = 2# ^ p# - 1#

c# = (m# - 1#) / (p#)

IF c# <> INT(c#) THEN PRINT p#; "is not prime.": SYSTEM

IF p# = 2# THEN GOTO lbla

IF p# MOD 6# = 5# THEN GOTO lbla

IF p# MOD 6# = 1# THEN GOTO lblb

lbla:

IF k# = 2# THEN k# = 4# ELSE k# = 2#

x# = x# + k#

y# = (c# - x#) / (x# * p# + 1#)

IF x# > y# THEN GOTO lblz

IF y# <> INT(y#) THEN GOTO lbla

IF y# = INT(y#) THEN c# = y#: GOSUB lbly: GOTO lbla

GOTO lblz

lblb:

IF k# = 4# THEN k# = 2# ELSE k# = 4#

x# = x# + k#

y# = (c# - x#) / (x# * p# + 1#)

IF x# > y# THEN GOTO lblz

IF y# <> INT(y#) THEN GOTO lblb

IF y# = INT(y#) THEN c# = y#: GOSUB lbly: GOTO lblb

GOTO lblz

lblz:

PRINT (c# * p# + 1#)

SYSTEM

lbly:

PRINT (x# * p# + 1#)

RETURN

Yes, further improvements can be made. Needs to be written in an assembly code with less limited number lengths.

Powered by vBulletin® Version 4.2.5 Copyright © 2019 vBulletin Solutions Inc. All rights reserved.