A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

anonymous

  • 5 years ago

yes, im still stuck on that primes problem. my code is this: http://dpaste.com/532787/ my bug begins after the 24th prime. for the 25th i get 95 and not 97. since my tuple contains all the #'s from 2 up to but not including the value being tested, and 95%5==0 is true, it should add 2 to the number again, but it doesn't. when i try running the for loop 999 time it gives me the 800 something th prime. i just can't seem to figure our the bug. my (tiny) brain has ben struggling with this problem for a tremendous amount of time. help.....

  • This Question is Closed
  1. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I couldn't really just find a single bug or an easy fix for your code so I kind of just rewrote it for you if you have any questions just ask. http://dpaste.com/hold/532804/

  2. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Double_o, your outer loop is only iterating 49 times, and your inner most one is making your divisor search skip a lot of possible divisors for some of the prime numbers. I think inserting a few print statements would make it pretty obvious where things are going wrong. Just put a line in a few different places to show where you are in the code and what the values of prime, div, and i are.

  3. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    sry i was using 49 to see if it would give me the 50th prime and forgot to fix it. but what do you mean that its skipping possible divisors? doesn't the range give the values from 2 up to but not including the upper value in range? sry im really slow sometimes

  4. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Yes, the range(2,prime) will give a list of numbers from 2 to prime, but inside that you're incrementing your prime variable and continuing to look for divisors from the list for the original prime, not the newly incremented one.

  5. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    ok, so your saying that the prime value in range(2, prime) is 3 throughout the entire loop?

  6. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    polpak had a good idea: try this out, http://dpaste.com/533072/ i put a few print statements in there - makes for a long listing but you can see that is actually "going wrong" a lot earlier even though it provides correct results - stop it from running with ctrl-c then scroll back to examine the output Heres a good example i=8 and prime = 25. http://dpaste.com/533073/ sometimes inside your while loop you change the number you are testing for primeness but div just keeps incrementing - it never goes back to check the 'new prime' for the lesser values of div. later on that might lead to problems. print statements rule!! was that while loop an attempt to optimize? optimization early to the dark side leads

  7. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    AH! the light just turned! on now i see what it is doing. thank you all for your help. now that i understand what it is doing wrong i might be able to fix it (hopefully)

  8. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    AH! the light just turned! on now i see what it is doing. thank you all for your help. now that i understand what it is doing wrong i might be able to fix it (hopefully)

  9. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    here's my updated code: http://dpaste.com/533273/ i added to more for loops so that it would update the upper end of the range. since it was able to give me the ten-thousandth prime correctly, im thinking that its ok for the purposes of this lesson. any comments? thanks polpak and bwCA

  10. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    me personally, i would not change two things inside of loops. because you are doing this you have to have multiple nested loops to go back and account for those changes which complicates the program and makes it hard to understand what's going on. check out the zen of python: http://www.python.org/dev/peps/pep-0020/ bottom line - if you get the right answers, you get the right answers. the purpose of the course is to learn how to think like a computer scientist and learning python is a side benefit (big one imo). the way you implemented this may work for a simple/small problem like primes but if you use that approach for larger/complex problems it might get real ugly. the caveat here is that i really don't have a lot of experience but i have written some ugly programs - that's why i'm taking the course. as the code gets more complicated, you should add more comments to explain what it is doing so that when you look at it next week you can figure out what it's doing. if You(!) think your code is starting to get ugly it might be time to regroup and rethink the solution. I can tell when this is happening to me when i keep having to go back and add all kinds of stuff to just MAKE IT grind away at a problem till it works. in this case, i would have an outer loop that changes prime and an inner loop that changes div. just my take tho - maybe someone else will jump in..

  11. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    thanks for the advice

  12. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    One of the things to start thinking about is Given some large problem, how can I decompose into a set of smaller problems. For this case, you need to find a bunch of prime numbers. To do that, you have to move through the set of potential primes, and test for primeness. So it breaks down into two smaller problems. Problem (1) move through the set of potential primes until we have found 1000 primes. Problem (2) test a given number to determine whether or not it is a prime. The solution to the first problem relies on the solution to the second, so start with the second problem first. If I give you a number testNum = 53982717637291, can you write a small bit of code that will determine if testNum is a prime number?

  13. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    well, you could take one of two approaches 1. divide by all numbers except 1 and the number u mentioned is prime. if there's no remainder for any of the numbers, then it is prime 2. check to see if any of the previous primes divide evenly into the number. if they do not, then the number is prime thats what immediately comes to mind

  14. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    But for the example I gave, you don't have any previous primes.

  15. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    then the only option is 1, but i don't think its a good method. honestly though, i can't see another way

  16. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    it would be like i did in my program where: for i in range(2, #): if # % i == 0: print "# is prime" else: print " # is not prime"

  17. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    opps i got that backwards for i in range (2, #): if # % i == 0: print "# is not prime" else: print "# is prime"

  18. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    That won't quite work right. First use testNum instead of # and imagine that testNum = 15. What will this code output?

  19. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    oh i didn't think that that would happen.......

  20. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Can you correct the problem?

  21. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    i tried this: testnum = 15 for i in range(2, testnum): if testnum % i == 0: testnum = 2 else: testnum = 0 if testnum <3 and testnum >1: print "not prime" else: print "prime" but its not correct because it testnum = 100 it still says prime... :(

  22. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Ok, lets take a step away from the code. Describe in english what you would do to determine if 15 was a prime number?

  23. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    wait, i just had a thought

  24. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    you could find the divisors to testnum and see if any of them are prime

  25. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Does it matter? If you find a divisor for testNum it is definitely not prime unless it's 1 or testNum.

  26. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Let me describe a process to you, and you tell me what you think. Loop for every number from 2 to testNum-1. If that number divides testnum, testnum is not prime If we get to the end before we found a divisor testnum is prime

  27. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Actually I don't like the word loop in that explanation, but oh well.

  28. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Does that process seem as though it does what we want?

  29. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    sounds right to me.....

  30. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    #Ok so you have the outer part down for i in range(2, testNum): #And also the part where we check if i divides testNum if testNum % i == 0: # What should we do here??

  31. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    i'd like to say that it's not prime, but i did that i nmy last cade and it didn't work so i'm kinda lost

  32. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Well you're right. We can say it's not prime. But what else do we need to do?

  33. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Should we continue searching?

  34. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    we need to kill the program

  35. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    We need to end the loop. Do you know of a way to end a loop early?

  36. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    sadly, no

  37. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Ok then. Do you know how to write a while loop?

  38. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    since ive only watched up to lesson 3 i only know about for loops

  39. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Ok then. Lets try this. Can we safely assume that a number is prime unless we find something showing it is not prime?

  40. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    oh wait u mean the "while something is true, do something" loop?

  41. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Yes. That is a while loop.

  42. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    ooooooooooh ok then i guess ive seen it before

  43. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Can you write a while loop that is the equivalent to for i in range(2, testNum):

  44. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    div = 2 while div < testnum and div >= 2: testnum % div # im still not quite whether to bind it to something, set it equal to something or something else so for the time being, i'll leave this portion incomplete div = div + 1

  45. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    do i need an if clause in there?

  46. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    No, that's great.

  47. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    One minor point (doesn't matter much) since div = 2 and you're adding to it inside the loop it will never be < 2. So the div >= 2 bit isn't needed.

  48. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    So for div in range(2, testNum): is the same as div = 2 while div < testNum: div = div+1

  49. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    never thought until today

  50. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    never thought about that until today*

  51. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    wait, since all the numbers being tested are odd, couldn't we set div = 1 in the beginning then increment it by 2 to get it to divide by all odd numbers, since no odd number is evenly divisible by an even one?

  52. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Sure, that'd save us some bad tests certainly.

  53. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    no that won't work we have to set it to 3 since it would evenly divide by 1

  54. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Yeah good point.

  55. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    But still, that's a decent optimization.

  56. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Ok, so now did you decide if it would be ok to assume that until we find a number which divides testnum, we can assume it is prime.

  57. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    yes i would think so

  58. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    We are trying to tell if testNum is prime because we plan to do something with that piece of information. So perhaps we should have a variable to keep track of that info. Something to indicate the 'primeness' of testNum so once we determine it, we don't have to test it again.

  59. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    What should we call that?

  60. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    are you suggesting to store the prime values in a tuple?

  61. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    No. I'm saying have a variable 'testNum_is_prime' or something that is True if testNum is prime, and False if it is not prime.

  62. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    im not sure i understand what you mean by storing and not testing again.

  63. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Well, we are looping over all the divisors right? And when we find one that divides testNum we know at that moment testNum is not prime. But after that moment is passed, how will we know? Once we've finished the loop, what can we do to see if we made it through successfully without finding a divisor or not?

  64. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    If we store that knowledge somewhere we can retrieve it later

  65. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    we could say something like prime = testnum if testnum is prime and not_prime if testnum is not prime

  66. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Sure. But we only know testnum is prime if we make it through EVERY divisor and don't find one that works. We know it is not prime if we find just 1 that works.

  67. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    So really we just need to know if it's not prime. Perhaps we can call the variable notPrime. if testNum % div == 0: notPrime = True

  68. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    but we can't assign to literal right?

  69. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    notPrime is just a variable name, like testNum or div

  70. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    i meant we can't assign a variable to something literal, but i found out we can call it true so never mind

  71. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    True is the universal truth object in python. Just like 1 is the universal unary object.

  72. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    So it's ok. If you prefer though you can do something like notPrime = 1

  73. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    sry i didn't know that

  74. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    So now we have our loop: div = 2 notPrime = 0 # We don't know so we assume it's prime while div < testNum: if testNum % div: notPrime = 1 if notPrime == 0: print testNum, "is prime" else: print testNum, "is not prime"

  75. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Whoops, I'm missing a few things.

  76. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I forgot to increment div, and you wanted to start div at 3 instead of 2. Can you fix it?

  77. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Did I lose ya?

  78. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    i meant we can't assign a variable to something literal, but i found out we can call it true so never mind

  79. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    not yet :) http://dpaste.com/533358/

  80. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Great except that the div = div+2 bit needs to not be part of the if block right? We always want to increment div

  81. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    http://dpaste.com/533360/

  82. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    right

  83. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Ok, now that should work well. Can you see any way we can optimize it further?

  84. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Oh, actually your version has a minor bug.

  85. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    if testNum % div:

  86. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    testNum % div will be True when?

  87. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    testNum % div == 0

  88. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    right. Otherwise it would do the opposite of what we want since 0 evaluates to False in a boolean context.

  89. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    oh ok sry about that

  90. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    but now i need to modify the program so that it will generate numbers, test to see if they are prime, then spit out the 1000th prime number right?

  91. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Certainly! But we already have some code to test for primeness, so all we have to do is take this code we have, and nest it inside some other loop that changes the value of testNum.

  92. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    so we could basically set testNum = 1 in the begnning , loop it to the desired prime-1, then keep testing the odd numbers?

  93. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Well you want the 1000th prime, so you need to keep a count of how many primes you find.

  94. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    oh yeah....

  95. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    do we use a tuple then?

  96. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    or range (1000)

  97. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    No, just a variable. testNum=3 primeCounter = 1 # Since we're skipping 2 while primeCounter < 1000: ... testNum = testNum + 2

  98. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    oh duh

  99. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Then when you find a prime (in addition to printing it) you can increment primeCounter.

  100. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    the ... is where our original code will go.

  101. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    with nearly no modification

  102. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    so if i basically stick all this together i can get any prime i need so long as i make primeCounter < anyVariable and have anyVariable = input("some sort of blah")?

  103. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Yes essentially.

  104. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    It will take longer, the farther you go because of the increased sparsity of primes

  105. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    But it will work

  106. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    thanks for all your help. now i think i see what i was supposed to. your a lifesaver

  107. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    of course!

  108. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    i'll be back when i need more help but thanks in advance :D

  109. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.