View Full Version : Programming Puzzle 20 - Display primes

ABC123

Tom Cone Jr

08-15-2011, 06:58 AM

Your manager has gone on sabbatical, but a colleague in the cubicle next door has been reading about "prime numbers". He's wondering if xbasic can be used to compute primes. You recall that a number is "prime" if it's an integer greater than 1 that can only be evenly divided by 1 or itself. For example, 2, 3, 5 and 7 are primes, but 4, 6, 8, and 9 are not.

Your challenge, grasshopper, is to write an xbasic script that will display the first 50 prime numbers in five lines, each of which contains ten numbers.

Have fun, your manager won't be back for a week!

jeb richardson

08-16-2011, 11:16 AM

puz 20 attempt

29078

Tom Cone Jr

08-16-2011, 12:30 PM

Thanks, Jeb.

Prof. Pickypicky will be happy to review your code when you add comments to explain the logic of your design.

-- tom

jeb richardson

08-16-2011, 03:08 PM

Prof. Pickypicky, I do apologize about the no comments. I feel as if I'm not good at commenting the script, but I guess that's why you are pushing us to do this. That way we can comment a script and come back to it later and know exactly what it does. Prof knows best. Well here's my revised and commented script. Hope this works. Thanks.

29088

P.S. as you know my script is very repetative. I went ahead and copied each comment to the corresponding line. Therefore, there is a lot of repeats. Just trying to prevent confusion. Thanks again.

Tom Cone Jr

08-16-2011, 05:42 PM

Jeb,

The professor thanks you for the thorough job you did documenting your code. Here are some suggestions for your consideration.

1) Remember that a string of text characters can be broken into lines for display on screen by inserting a crlf() in the string wherever you want a carriage return/linefeed to appear. Instead of duplicating the code processing for each of the 5 lines you want to generate, why not run the numbers once until you find all 50 primes, building your output string as you go. A simple counter would let your script know when 10 numbers have been inserted into the string, so the script could then do a " + crlf() + " and continue.

2) Finding prime numbers has been studied a lot and mathematicians are often challenged to find the most efficient way. In your case the Prof sees a couple of easily remedied inefficiencies. In your design you test each number by dividing it by both the integer 1 and itself. These 2 "factors" are always present. You determine a number is prime if there are only "2" factors that can evenly divide the candidate number. Consider the savings that could be achieved if you never divided the number by 1 ? Dividing by 1 tells you nothing. You know 1 is always going to be a factor right? So most would begin their divisions with "2", skipping "1" entirely. Not a big savings in our small sample, but if you were trying to produce a list of the first 10,000 primes... ? Also, consider that in any case where the denominator is greater than half the numerator an even division is impossible. Say, for example, we're trying to see if "11" is prime. We need to divide by 5. But do we ever need to divide by "6", "7", "8", "9", or "10". Won't all these divisions by definition always have a remainder? If so there's no need to see they could be a factor of the candidate. In your design you continue dividing past the mid-point, even though all those divisions will always have a remainder. So, recognizing this most would limit the loop that tests for factors so that it stops when it gets to a number thats greater than half the candidate being tested. i.e

int(Candidate_Nbr / 2) The savings here becomes huge as the candidate numbers get larger and larger. Half of the loops you currently are using can be omitted. See?

jeb richardson

08-17-2011, 09:54 AM

29096

Prof Pickypicky,

This is my script with some changes to it. I have got my script to now only look for one factor because t_val is always a factor of t_val. Therefore, I have it finding how many other factors it has. So, now if it only has one factor (itself not included) it's a prime. Also, I have shortned it. Check it out. Hope this is much better. Thanks.

P.S. still working on the divisor greater than half the t_val. It's line 20 in this script it is commented out.

Tim Kiebert

08-17-2011, 10:46 AM

Dear Professor Pickypicky,

I humbly submit this code for your consideration.

I await, primed for your response.

TJK

Tom Cone Jr

08-17-2011, 12:28 PM

Tim,

The Professor is impressed that you skipped all the EVENLY numbered candidates. No reason to test them is there?

Your approach gets the correct answer, but is based on an hypothesis for which no proof is offered.

' The largest divisor needed to test. This is found by getting the integer of the

' square root of the number being tested. Any value larger than this integer that

' divides evenly would have been the result of a division by a number smaller

' than the root

On behalf of the mathematically challenged the Professor is curious. What proof might be offered that this is a true statement in all cases?

-- tom

PS - Kudos on the comments in your code! An excellent example. Worthy of being framed and displayed on the mantle for all to follow.

Mike Wilson

08-17-2011, 07:39 PM

Funny, I thought about skipping all even numbers also. I didn't think there was a proof needed, it's a mathematical truth, like the definition of a prime number, an even number is that which can be divided by 2 with no remainder. So I'm guilty too.

Tim Kiebert

08-17-2011, 09:08 PM

Mike,

I think prof Pickypicky is referring to the use of the square root as the upper limit that needs testing not the elimination of even numbers.

Tim Kiebert

08-17-2011, 09:24 PM

Professor Pickypicky,

Thanks for the feed back.

With regards to the not giving of proof for the 'square root upper limit' theory, I had to leave an obvious issue to distract you from all the other short comings. :wink:

It is something I remembered from the distant past.

Actually, I thought that you would pick me up on the assumption that 2 is a prime number.

I will try to put together an explanation for this. I am not a mathematician so the best I can probably come up with is a general description of the idea with some examples. ('All' when playing with numbers can be a long list) I might also cheat and take a look at wikipedia for some references. I may have to ask for an extension because Professor DayJob has given this student way too many assignments. :sad:

TJK

Mike Wilson

08-18-2011, 10:32 AM

I recognized this later and believed I added this as a Later: edit statement in my post, but it didn't get through apparently.

I added a 5th premise to skip testing 2 digit values with both characters being the same number except 11 because those will always be divisible by 11. This applies to 4 digit numbers where first and last digits are the same value but middle 2 digits are either one greater (1221,2332,) or one less (2112,3223,5445). Not sure this removes too much more time from processing. But kick me in the shins when I have to come up with a proof of this for Professor Pickypicky. :grin:

Tim Kiebert

08-18-2011, 11:48 AM

Nice addition MIke,

I haven't provided a proof for my last hypothesis yet but while on a break from my assignments for professor Dayjob I thought of something else. Since even numbers are divisible by two and therefore not prime numbers, may be divisors that are even can also be eliminated from the processing. In other words, any number that is divisible by an even number is also divisible by two, and therefore not a prime.

I changed the line

CurrDivisor = CurrDivisor + 1 (line 65)

to

CurrDivisor = CurrDivisor + 2

and added an additional count of process steps at line 49 and 55 (TestsDone = TestsDone + 1)

changing line 65 reduced the process steps from 525 to 307

The results did not change. I wonder if that is enough proof. :thinking:

Mike Wilson

08-18-2011, 12:41 PM

Excellent Tim!

StephenP

08-19-2011, 12:00 AM

I humbly submit my homework. I explain my change of display format. I didn't peek at others desks while working.

BTW, I love prime numbers. My sister once told me that she, her husband and all four of their kids were all prime numbers for several months between birthdays. Jealousy coursed through my veins!

StephenP

08-19-2011, 12:08 AM

After reading through the other posts after submitting mine, I see that I must prove the Prime Root Theorem. I will do my best and post it later. As Fermat says, I have a simple proof, but it is too big to type up right now.

RRTRACKS

08-19-2011, 03:28 AM

I do not have much background in math so my proof of the prime square theorem is probably off, but here goes my best shot.

A = Sqrt of B

B = A * A

B < A * (A + 1)

Therefore where X > A and B = X*Y,

Y must be less than or equal to A, the square root of B, otherwise the product would be greater than B.

I look forward to seeing what the correct format and content of this proof is going to be.

Thanks to all for the participation here. If I can ever find the time to sit down and learn Xbasic, it is going to be invaluable.

Rich Pasma

The edit was for when I realized I messed up. It is still not perfect but seems to be headed in the right direction.

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