Write a program that obtains the execution time for finding all the prime number

Question

Write a program that obtains the execution time for finding all the prime numbers less than 8,000,000, 10,000,000, 12,000,000, 14,000,000, 16,000,000, and 18,000,000 using the algorithms in Listings 16.4-16.6. Your program should print a table like this: Write a program that prompts the user to enter two strings and tests whether the second string is a substring in the first string. (Don't use the find method in the str class.) Analyze the time complexity of your algorithm. Here is a sample run of the program: Enter a string S1: Mississippi Enter a string S2: sip matched at index 6 (Same-number subsequence) Write an o(n) program that prompts the user to enter a sequence of integers and finds longest subsequence with the same number. Here is a sample run of the program: Enter a series of numbers ending with 0: 2 4 4 8 8 8 8 2 4 4 0 The longest same number sequence starts at index 3 with 4 values of 8 (Execution time for GCD) Write a program that obtains the execution time for finding the GCD of every two consecutive Fibonacci numbers from the index 40 to index 45 using the algorithms in Listings 16.2 and 16.3. Your program should print a table like this: import time startTime = time.time () #whatever you want to time, put it here time.sleep (3) # sleep for 3 seconds endTime = time.time() elapsed = endTime - startTime print ("It took", elapsed, "second to run")

Explanation / Answer

There are always more efficient ways to solve various classical math tasks than we may even guess.

So my first solution to find out a prime number was a pure "Pythonical" :-)

But with very exciting book (in Russian) "Modern programming from scratch" by V.Potopahin (. " ") I realized a classical algorithm in Python and... some thoughts.

Of course there is no sense to seek for an aliquot part in full range from 2 to x - 1, i.e for i in range(2, x):. It would be unnecessary to count, e.g. 10 % 6, 10 % 7, ... , 10 % 9. So we only need half a range, i.e. for i in range(2, x // 2 + 1): We may use simple devision x / 2 for the second parameter, as far as in Python integer division returns the floor, but I use explicit floor devision operator x // 2 to be more universal/academic. You may/must get acquainted with Binary arithmetic operations, though.

But let's go further. It is interesting, every desired number's divisor has its own pair. For instance, 100 has the following pairs (2; 50), (4; 25), (5; 20), (10; 10). Every divisor in a pair converges to 10, the left divisor goes in ascending order while the right one goes descending. 10 is a square of 100.

Therefore, we find the minimal range of [2, sqrt(x)]. But we can not use it in for loop like for i in range(2, sqrt(x) + 1):, so far as sqrt(x) returns a float. And it is great! Then we automatically make use the classical approach, i.e. while k <= sqrt(x) and prime == True:, where we can compare integer and float with any conditional oprerator and there is no need in any atavisms like goto, break, continue operators and in multiple returns.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.