a. Write a program to determine if a positive integer, N, is prime. b. In terms of

Question:

a. Write a program to determine if a positive integer, N, is prime.

b. In terms of N, what is the worst-case running time of your program? (You should be able to do this in O(√N).)

c. Let B equal the number of bits in the binary representation of N. What is the value of B?

d. In terms of B, what is the worst-case running time of your program?

e. Compare the running times to determine if a 20-bit number and a 40-bit number are prime.

f. Is it more reasonable to give the running time in terms of N or B? Why?

Fantastic news! We've Found the answer you've been seeking!

Step by Step Answer:

Related Book For book-img-for-question

Data Structures and Algorithm Analysis in Java

ISBN: 978-0132576277

3rd edition

Authors: Mark A. Weiss

See More Books

Question Posted: Mar 06, 2018 09:35 AM

See More Questions

Write a small program to determine the endianness of machine and report the results. Run the program on a computer available to you and turn in the output.
Write a simple TCP program for a server that accepts lines of input from a client and prints the lines onto the server's standard output. (You can do this by modifying the TCPServer java program in...
Write a program that receives an ASCII code (an integer between 0 and 127) and displays its character. For example, if the user enters 97, the program displays the character a. Here is a sample run:...
Using the following information, determine the activity rate for the quality inspections activity. Budgeted Activity Cost Pool Activity Setups Estimated Activity Base 1,000 $60,000 Purchase orders...
A skier from rest at A (30 ft, O) and descends the smooth slope, which may be approximated by a parabola. If she has a weight of 120 lb, determine the normal force she exerts on the ground at the...
Questions 5-8 refer to the following passage. Select the sentence that attempts to correct a possible misconception about the effects of solar winds. "Solar wind" is the term scientists use to...
As can be easily verified by means of the formula for the binomial distribution, the probabilities of getting 0 , 1,2 , or 3 heads in 3 flips of a coin whose probability of heads is 0.4 are...
Analyze the following independent situations. a. Sophia, Inc. is being sued by a former employee. Sophia believes that there is a remote chance that the employee will win. The employee is suing...
Discuss the key components of an environmental analysis, determining the status of external factors that will impact the company's offerings.
Yount Co. has equipment that cost $50,000 and that has been depreciated $22,000. Record the disposal under the following assumptions. (a) It was scrapped as having no value. (b) It was sold for...
Suppose T1(N) = O(f (N)) and T2(N) = O(f (N)). Which of the following are true? a. T1(N) + T2(N) = O(f (N)) b. T1(N) T2(N) = o(f (N)) c. T1(N) / T2(N) = O(1) d. T1(N) = O(T2(N))
The Sieve of Eratosthenes is a method used to compute all primes less than N. We begin by making a table of integers 2 to N. We find the smallest integer, i, that is not crossed out, print i, and...
The Roadnet Transport Company expanded its shipping capacity by purchasing 90 trailer trucks from a bankrupt competitor. The company subsequently located 30 of the purchased trucks at each of its...
1. The data shows the scores obtained by 33 participants in a quiz. 36 37 37 20 52 11 40 15 25 29 51 40 63 32 45 34 49 68 33 31 41 50 60 59 43 18 44 39 32 64 21 56 13 Using Sturges Rule, construct a...
A pharmaceutical company is testing a new drug. Of the 110 people that received the drug, 61 of the people's autoimmune disease went into remission. Using the old drug the autoimmune disease for 50%...
(Creation of payoffs using options) Consider the following three call options on a non- dividend-paying stock expiring in T: Strike K1-$17/share K2=$20/share K3=$23/share Premium $5.00/share...
1. Chaka Furniture makes chairs, arm-chairs and sofas, the profits are Php 60 per chair, Php 70 per arm-chair and Php 90 per sofas. The material used to manufacture these items are fabric and wood. A...
(Option Strategies/Arbitrage Strategy) Consider the following three European put options with the same underlying non-dividend paying stock and the same expirations: The first put option has a strike...
Emily Jackson (Social Security number 765-12-4326) and James Stewart (Social Security number 466-74-9932) are partners in a partnership that owns and operates a barber shop. The partnerships first...
Proposals have been made to ?sail? spacecraft to the outer solar system using the pressure of sunlight, or even to propel interstellar spacecraft with high-powered, Earth-based lasers. Sailing...
What is an assignment problem?
What are the three required parameters of a Solver model and what do they represent?
What are two advantages of creating a constraints table in a worksheet that includes a Solver model?
Jenny wishes to accumulate $10000 over 5 years for an overseas trip. She will make a deposit every 6-months, and the funds will earn the interest rate of 4% per annum compounded semi-annually. How...
Write a short C++ program that will prompt the user and input three integer values (month, day, year) from the console in a "date" format that includes '/' separator characters. e.g., 8/21/2013. Your...
Aimee is the owner of a stock with annual returns of 12.3 percent, -5.0 percent, 6.6 percent, and 18.2 percent for the past four years. She thinks the stock may achieve a return of 27 percent this...

a. Write a program to determine if a positive integer, N, is prime. b. In terms of

Question:

Step by Step Answer:

a Test to see if N is an odd number or 2 and is not divisible by b as...View the full answer

Data Structures and Algorithm Analysis in Java

Students also viewed these Computer Sciences questions