Alpha DevCon 2018
Results 1 to 17 of 17

Thread: Programming Puzzle 20 - Display primes

  1. #1
    "Certified" Alphaholic
    Real Name
    Tom Cone Jr
    Join Date
    Apr 2000
    Location
    Florida
    Posts
    23,299

    Default Programming Puzzle 20 - Display primes

    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!

  2. #2
    Member
    Real Name
    Jeb Richardson
    Join Date
    Aug 2011
    Location
    Bowling Green, KY
    Posts
    26

    Default Re: Programming Puzzle 20 - Display primes

    puz 20 attempt

    puz 20.txt

  3. #3
    "Certified" Alphaholic
    Real Name
    Tom Cone Jr
    Join Date
    Apr 2000
    Location
    Florida
    Posts
    23,299

    Default Re: Programming Puzzle 20 - Display primes

    Thanks, Jeb.

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

    -- tom

  4. #4
    Member
    Real Name
    Jeb Richardson
    Join Date
    Aug 2011
    Location
    Bowling Green, KY
    Posts
    26

    Default Re: Programming Puzzle 20 - Display primes

    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.

    puz 20.txt

    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.

  5. #5
    "Certified" Alphaholic
    Real Name
    Tom Cone Jr
    Join Date
    Apr 2000
    Location
    Florida
    Posts
    23,299

    Default Re: Programming Puzzle 20 - Display primes

    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
    Code:
     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?

  6. #6
    Member
    Real Name
    Jeb Richardson
    Join Date
    Aug 2011
    Location
    Bowling Green, KY
    Posts
    26

    Default Re: Programming Puzzle 20 - Display primes

    puz 20-3.txt

    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.
    Last edited by jeb richardson; 08-17-2011 at 11:14 AM.

  7. #7
    "Certified" Alphaholic Tim Kiebert's Avatar
    Real Name
    Tim Kiebert
    Join Date
    Jul 2004
    Location
    Geelong, Victoria, Australia
    Posts
    2,784

    Default Re: Programming Puzzle 20 - Display primes

    Dear Professor Pickypicky,

    I humbly submit this code for your consideration.

    I await, primed for your response.

    TJK
    Attached Files Attached Files
    Tim Kiebert
    Geelong Citrus Packers
    A complex system that does not work is invariably found to have evolved from a simpler system that worked just fine.

  8. #8
    "Certified" Alphaholic
    Real Name
    Tom Cone Jr
    Join Date
    Apr 2000
    Location
    Florida
    Posts
    23,299

    Default Re: Programming Puzzle 20 - Display primes

    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.
    Last edited by Tom Cone Jr; 08-17-2011 at 11:40 AM.

  9. #9
    "Certified" Alphaholic Mike Wilson's Avatar
    Real Name
    mike wilson
    Join Date
    Apr 2005
    Location
    Michigan
    Posts
    4,126

    Default Re: Programming Puzzle 20 - Display primes

    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.
    Attached Files Attached Files
    Mike W
    __________________________
    "I rebel in at least small things to express to the world that I have not completely surrendered"

  10. #10
    "Certified" Alphaholic Tim Kiebert's Avatar
    Real Name
    Tim Kiebert
    Join Date
    Jul 2004
    Location
    Geelong, Victoria, Australia
    Posts
    2,784

    Default Re: Programming Puzzle 20 - Display primes

    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
    Geelong Citrus Packers
    A complex system that does not work is invariably found to have evolved from a simpler system that worked just fine.

  11. #11
    "Certified" Alphaholic Tim Kiebert's Avatar
    Real Name
    Tim Kiebert
    Join Date
    Jul 2004
    Location
    Geelong, Victoria, Australia
    Posts
    2,784

    Default Re: Programming Puzzle 20 - Display primes

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

    TJK
    Last edited by Tim Kiebert; 08-17-2011 at 08:34 PM.
    Tim Kiebert
    Geelong Citrus Packers
    A complex system that does not work is invariably found to have evolved from a simpler system that worked just fine.

  12. #12
    "Certified" Alphaholic Mike Wilson's Avatar
    Real Name
    mike wilson
    Join Date
    Apr 2005
    Location
    Michigan
    Posts
    4,126

    Default Re: Programming Puzzle 20 - Display primes

    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.
    Attached Files Attached Files
    Mike W
    __________________________
    "I rebel in at least small things to express to the world that I have not completely surrendered"

  13. #13
    "Certified" Alphaholic Tim Kiebert's Avatar
    Real Name
    Tim Kiebert
    Join Date
    Jul 2004
    Location
    Geelong, Victoria, Australia
    Posts
    2,784

    Default Re: Programming Puzzle 20 - Display primes

    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.
    Attached Files Attached Files
    Tim Kiebert
    Geelong Citrus Packers
    A complex system that does not work is invariably found to have evolved from a simpler system that worked just fine.

  14. #14
    "Certified" Alphaholic Mike Wilson's Avatar
    Real Name
    mike wilson
    Join Date
    Apr 2005
    Location
    Michigan
    Posts
    4,126

    Default Re: Programming Puzzle 20 - Display primes

    Excellent Tim!
    Mike W
    __________________________
    "I rebel in at least small things to express to the world that I have not completely surrendered"

  15. #15
    Member StephenP's Avatar
    Real Name
    Stephen Pilon
    Join Date
    Apr 2000
    Location
    Front Royal, Virginia
    Posts
    490

    Default Re: Programming Puzzle 20 - Display primes

    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!
    Attached Files Attached Files
    Stephen Pilon
    Associate Librarian
    Christendom College

  16. #16
    Member StephenP's Avatar
    Real Name
    Stephen Pilon
    Join Date
    Apr 2000
    Location
    Front Royal, Virginia
    Posts
    490

    Default Re: Programming Puzzle 20 - Display primes

    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.
    Stephen Pilon
    Associate Librarian
    Christendom College

  17. #17
    Member
    Real Name
    Rich Pasma
    Join Date
    Dec 2008
    Posts
    43

    Default Re: Programming Puzzle 20 - Display primes

    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.
    Last edited by RRTRACKS; 08-19-2011 at 02:45 AM.

Similar Threads

  1. Programming Puzzle 2 - Another Simple Loop
    By Tom Cone Jr in forum Xbasic Programming Puzzles
    Replies: 16
    Last Post: 12-20-2014, 10:38 AM
  2. Programming Puzzle 1 - Simple Loop
    By Tom Cone Jr in forum Xbasic Programming Puzzles
    Replies: 32
    Last Post: 12-26-2011, 01:38 PM
  3. Programming Puzzle 3 - Fractions, anyone?
    By Tom Cone Jr in forum Xbasic Programming Puzzles
    Replies: 7
    Last Post: 11-08-2011, 05:40 AM
  4. Programming Puzzle 11 - More Loops
    By Tom Cone Jr in forum Xbasic Programming Puzzles
    Replies: 11
    Last Post: 08-20-2011, 04:50 PM
  5. Programming Puzzle 7 - Yet another nested loop!
    By Tom Cone Jr in forum Xbasic Programming Puzzles
    Replies: 4
    Last Post: 08-08-2011, 05:41 PM

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •