Please please please help me with Problem set 1! I don't know what to do when it comes to computing the 1000th prime... If anyone wants to be amazing, can they explain it maybe? Thanks!
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 :)
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.
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
Ok, so the first thing you should do is building the algorithm. Not in code, in text. What do you want to do? Let's make it easy and say you want the 10th prime. How can you separate this problem?
I would take a test number, and see if it's prime by dividing by the prime components (2, 3), and if it's prime print it and add it to a list of primes to check the next number.
x = 3
count = 1
while count < 1000:
for x in range(1, x+1):
for y in range(1, x):
if y % x == 0:
else: x = x + 1
count = count + 1
I wrote this. It doesn't work, but it seems like it might have the write idea? Please help anyway you can :)
Not the answer you are looking for? Search for more explanations.
Ok, my first step would be this:
Given an number x, check if it is prime.
Also, check the definition of a prime number: "A natural number (i.e. 1, 2, 3, 4, 5, 6, etc.) is called a prime number (or a prime) if it has exactly two positive divisors, 1 and the number itself".
This is a list of prime numbers: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173.
You should start with the smaller ones (2,3,5,7,11) as tests, and then try with some bigger numbers.
So first write a code that tells you: Hey, this number is prime! And then focus on the second part of the problem (finding the nth prime)
x = raw_input("Number: ")
x = int(x)
isPrime = True
for y in range(2, x):
if x%y == 0:
isPrime = False
if isPrime == True: print "Your number is prime"
I wrote this, and it works for all numbers I've tested except for squares of primes, but it prints "Your number is prime" multiple times... Don't know why... Do you have any way to remedy this? Sorry for all the questions, I'm way new to this... Thanks for all your help!
The if isPrime == True: print "Your number is prime" is inside the for, it should be outside :)
In general, what they want is for you to divide by numbers to see if you get a remainder or not. If there is a remainder, it did not divide in and therefore it might be prime. If there is not a remainder, it is not prime.
You do not need to test even numbers, so you can start at 3 and work up. Just remember to adjust your count because you are skipping 2 and only need to find 999 more primes.
If you skip even numbers, you do not need to divide by even numbers. See, anything divisible by 10, 44, or 186 is also divisible by 2.
You only need to teest half the numbers below a number... well... it is actually less than that, but let me talk about the logic. No number will divide evenly by a number that is more than half of it. So you can eliminate a ton of testing by setting the upper bounds of every test to n/2 where n is the number being tested.
Thank you for helping me! I'm actually falling in love with cs because of this challenging problem! (and it's not even supposed to be that hard! ;P) can't wait to continue