anonymous
  • anonymous
I'm stuck on ps1a How do I test if a particular candidate is prime? I understand that I need to check if there is a remainder when I divide by any integer>1, but how do I actually structure that test?
MIT 6.00 Intro Computer Science (OCW)
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
chestercat
  • chestercat
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
anonymous
  • anonymous
well the basic idea is to check all odd numbers before your number to see if any of them is a divisor of course u dont need to test ALL but you can set a limit to it
anonymous
  • anonymous
Not only odd - 2 too. And up to a certain limit, which is way lower than the number you test.
anonymous
  • anonymous
forget the 2 the assignment requires that you filter the odds out first anyway so basically you start with 3, then do your if condition to see if there is a remainder for all the divisions up to the variable you#re trying to determine (for loop with a counter). if so it means prime if not break...hope it helps

Looking for something else?

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

More answers

anonymous
  • anonymous
@Beeb - The assignment doesn't require that you generate only odd numbers to test, it merely suggests it. Of course, testing only odd numbers would be more efficient. However, ps1b will require that 2 be included in the list of primes to get a correct answer. @jaron - I've attached my ps1a, if you'd like to take a look. It is very inefficient, but it works.
1 Attachment
anonymous
  • anonymous
Opps, sorry for the double post.
anonymous
  • anonymous
from an algorithmic efficiency point of view I find the filtering out of the evens quite a bonus and the 2 as a gain for not doing so not very important. One can just add it via append (see below)since it is an obvious simple prime case...and this is a program not a math course. Plus it makes the filtering a tad easier and the running through way more efficient. Here is my old piece of code.... # prime.py # finds primes up to 1000 list=[] for k in range(1001): #since it would otherwise just go to 999 due to range if ((k%2)==1): #takes the odd ones for j in range(2,k+1): #loops through all variables from 2 to k if( ((k%j)==0) and j
anonymous
  • anonymous
One can simplify the number of divisor to go through by limiting the divisor to be other primes smaller than the current number. See the attach file for a way to do this.
1 Attachment
anonymous
  • anonymous
i tried it and it didn't work ...it gave me only 2 many times and didn't stop
anonymous
  • anonymous
ranlab, Did you check to make sure your indentation is correct? e.g. the num+=2 statement is at the first level under the while and not inside the if.
anonymous
  • anonymous
oh sorry i tried it again now and it worked but i don't think we took this in lectures till now. I mean break and append...can you expalin the code please. Thanks a lot
anonymous
  • anonymous
ranlab, "break" is a statement that stops the current loop from going into the next iteration. In this case it stops the "for i in primes:" loop, NOT the "while count<1000:" loop. I used this as a shortcut way to stop additional iterations in the "for" loop, because we have just found a divisor that results in no remainder. The "append" method adds a element to the end of a list. So "primes.append(num)" adds "num" as the last element to list "primes".
anonymous
  • anonymous
ok thanks a lot. which lectures are you in or you finished python
anonymous
  • anonymous
I'm on lecture 22. But just started to work on the problem sets.
anonymous
  • anonymous
ok good luck...i thought we can study together but its way too far. i am in lecture 4 :D
anonymous
  • anonymous
Thank you all for the help. I am starting to understand the logic and wrote something that prints out some numbers...but the first one it gives is 21! What am I doing wrong here? testNum = 3 y = 1000 while(y>0): for i in range(2, testNum): if testNum % i ==0: print testNum y = y - 1 testNum = testNum + 2 if testNum % i !=0: testNum = testNum + 2 print testNum
anonymous
  • anonymous
An if after another based on variable changed in the first if could be your problem, so it fulfils the first if and then updates testNum and then questions testNum again which gets fulfilled maybe and adds again. If it goes directly to your second if and adds two to testNum then goes into your for loop again...leading to not finding the desired result.... I would suggest you put a print statement under every step so that you see the flawed logic and avoid two ifs in a row, do an elsif...also take a look at the prior codes posted to see how they use the variables they define.
anonymous
  • anonymous
hm...if you want to test x, if there's no divisor from 3 to x/2 -> x is a prime. Hope that helps :) you can also consider testing 2,3,5,7 to reduce the problem to 1/7.

Looking for something else?

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