Prime Calculation

Question

Now I'm doing work in the field of MIT, and for the second task, I feel that it left me in the cold. http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00-introduction-to-computer-science-and-programming-fall-2008/assignments/pset1a.pdf

The specificity of this is to write something that can calculate the 1000th number. We only know about the print, ==, =, 1 =, if, else, elif, while,%, -, +, *, / commands that I think. We also do not know about importing libraries.

My idea of ​​how this will work is to take an odd number and try to divide it by 3,4,5,6,7,8,9, and if% n! = 0, then add the number to the NumberofPrimes variable, starting with 11 as the basis of the tests, and assigning it a base value of 4 in the NumberofPrimes database, although I do not know if this is even correct, because I do not know how to display the 1000th number.

I close?

The last incarnation is this:

##calculate the 1000th prime number potprime = 3 numberofprime = 1 cycle = if potprime%3 = 0: break if potpimre%4 = 0: break if potprime%5 = 0: break if potprime%6 = 0: break if potprime%7 = 0: break if potprime%8 = 0: break if potprime%9 = 0: break numberofprime + 1 potprime + 1 if potprime%2 == 0: potprime = potprime + 1 if potprime != 0: cycle 

Where exactly am I mistaken? Walk me through this step by step. I really want to find out, although I feel like they just catch a cold here.

At this point, it would be more useful for me to see how you can do the right one, and not do it. I work for 3 hours and did not go anywhere. If anyone has a solution, I would be more than happy to look at it and try to learn from it.

Answer 1

Looks like I'm late

It is quite obvious that if a number is not divisible by any prime number, then this number itself is a prime number. You can use this fact to minimize the number of divisions.

To do this, you need to save a list of primes. And for each number, just try to split with primes already in the list. To further optimize it, you can drop all primes greater than the square root of the number to be tested. You will need to import the sqrt () function for this.

For example, if you are testing 1001, try testing 3, 5, 7, 11, 13, 17, 19, 23, 29, and 31. That should be enough. Also, never try to figure out if an even number is prime. So basically, if you check the odd number n, then after this test the following number: (n + 2)

Test the code below. The 1000th is 7919. Not a big number!

The code may look like this:

 from math import sqrt primeList = [2] num = 3 isPrime = 1 while len(primeList) < 1000: sqrtNum = sqrt(num) # test by dividing with only prime numbers for primeNumber in primeList: # skip testing with prime numbers greater than square root of number if num % primeNumber == 0: isPrime = 0 break if primeNumber > sqrtNum: break if isPrime == 1: primeList.append(num) else: isPrime = 1 #skip even numbers num += 2 # print 1000th prime number print primeList[999] 

Answer 2

The following code is important, but since 1000 is really a small index, it solves your problem in a split second (and uses only the primitives you should know so far):

 primesFound = 0 number = 1 while primesFound < 1000: number = number + 1 # start from 2 # test for primality divisor = 2 numberIsPrime = True while divisor*divisor <= number: # while divisor <= sqrt(number) if number % divisor == 0: numberIsPrime = False break divisor = divisor + 1 # found one? if numberIsPrime: primesFound = primesFound + 1 print number 

You can test the solution here . Now you have to find a more effective solution, optimize and, possibly, go to the 1,000,000th prime ...

Answer 3

First, I'm sure in Python, if you want to have an if statement that checks if A = B, you need to use the == operator, not the =.

On the other hand, your algorithm will consider the number 143 simple, although 143 = 11 * 13

You need to keep track of all the prime numbers that you have already calculated - add them to the array. Use this array to determine if the new number you are testing is simple.

Answer 4

It seems to me that you jump to the deep end when you decide that the children's pool is too deep. A project with a simple number will assign 2 or 3 in most beginner programming classes immediately after the main syntax. Instead of helping you with the algorithm (there are a lot of good ones), I am going to suggest that you study the syntax with the python shell before writing long programs, since debugging a line is easier than debugging the whole program. Here is what you wrote in a way that will actually execute:

 count = 4 n = 10 #I'm starting you at 10 because your method #says that 2, 3, 5, and 7 are not prime d = [2, 3, 4, 5, 6, 7, 8, 9] #a list containing the ints you were dividing by def cycle(n): #This is how you define a function for i in d: #i will be each value in the list d if not n%i: #this is equal to if n%i == 0 return 0 #not prime (well, according to this anyway) return 1 #prime while count < 1000: count += cycle(n) #adds the return from cycle to count n += 1 print n - 1 

The answer is still incorrect because it is not like checking for simple. But knowing a little syntax will at least give you the wrong answer, which is better than a lot of traces.

(In addition, I understand lists, for loops and functions there wasn’t a list of things that you say you know.)

Answer 5

Your code for this answer can only be reduced to this:

 prime_count = 1 start_number = 2 number_to_check = 2 while prime_count <= 1000: result = number_to_check % start_number if result > 0: start_number +=1 elif result == 0: if start_number == number_to_check: print (number_to_check) number_to_check +=1 prime_count +=1 start_number =2 else: number_to_check +=1 start_number = 2 

Answer 6

To answer your next question: "How can I track all primes?

One way to do this is to create a list.

 primeList = [] # initializes a list 

Then, every time you check a number to see if it is prime or not, add that number to primeList

You can do this using the add function.

 primeList.append( potprime ) # adds each prime number to that list 

Then you will see a list filled with numbers, so after the first three primes it looks like this:

 >>> primeList [11, 13, 17] 

Answer 7

Your math fails. A prime number is a number consisting of 2 divisors: 1 and itself. You do not check numbers for simplicity.

Answer 8

I'm very late for this, but maybe my answer will be useful to someone. I am doing the same open course at the Massachusetts Institute of Technology, and this is the solution I came across. It returns the correct 1000th number and the correct 100,000th prime number and various others between the ones I tested. I think this is the right solution (not the most effective, I'm sure, but a working solution, I think).

 #Initialise some variables candidate = 1 prime_counter = 1 while prime_counter < 1000: test = 2 candidate = candidate + 2 # While there is a remainder the number is potentially prime. while candidate%test > 0: test = test + 1 # No remainder and test = candidate means candidate is prime. if candidate == test: prime_counter = prime_counter + 1 print "The 1000th prime is: " + str(candidate) 

While I was on it, I continued and completed the second part of the assignment. The question is asked as follows:

"There is a nice result from number theory, which claims that for sufficiently large n the product of primes less than n is less than or equal to e ^ n and that as n increases, this becomes dense (that is, the ratio of the product of primes to e ^ n approaches 1 with increasing n). Computing the product of a large number of primes can lead to a very large number, which can cause problems with our calculations. (We will talk about how computers deal with numbers a little later in terms.) Thus, we can predominate the product of a set of primes in the sum of the logarithms of primes, applying the logarithms to both sides of this hypothesis, in which case the above hypothesis reduces to the assertion that the sum of the logarithms of all primes less than n is less than n, and when n increases, the ratio of this sum to n is close to 1. "

Here is my solution. I print the result for every 1000th prime to 10,000th.

 from math import * #Initialise some variables candidate = 1 prime_counter = 1 sum_logs = log(2) while prime_counter < 10000: test = 2 candidate = candidate + 2 # While there is a remainder the number is potentially prime. while candidate%test > 0: test = test + 1 # No remainder and test = candidate means candidate is prime. if candidate == test: prime_counter = prime_counter + 1 # If the number is prime add its log to the sum of logs. sum_logs = sum_logs + log(candidate) if prime_counter%1000 == 0: # For every 1000th prime print the result. print sum_logs," ",candidate," ",sum_logs/candidate print "The 10000th prime is: " + str(candidate) 

Greetings

Adrian

Answer 9

I came up with this solution in my interview, but I did not get the job :( It has about 1/100 less iterations than the higher:

 from math import * MAX_IDX=1000 MAX_IDX-=1 num_iter=0 l_pirme_list=[3] candidate=l_pirme_list[0] prime_counter=1 while prime_counter < MAX_IDX: candidate+=2 #Cut the binary number in half. This is quite faster than sqrt() bin_candidate=format(candidate, "2b") max_prime_search=int(bin_candidate[:len(bin_candidate)/2+1],2)+1 # max_prime_search=sqrt(candidate)+1 candidate_is_prime=1 for prime_item in l_pirme_list: num_iter+=1 if candidate % prime_item==0: candidate_is_prime=0 break elif prime_item > max_prime_search: candidate_is_prime=1 break if candidate_is_prime: prime_counter+=1 l_pirme_list.append(candidate) l_pirme_list.insert(0,2) print "number iterations=", num_iter print l_pirme_list[MAX_IDX]