Question

In: Computer Science

A positive integer N is a power if it is of the form q^k, where q,...

A positive integer N is a power if it is of the form q^k, where q, k are positive integers and k > 1. Give an efficient algorithm that takes as input a number N and determines whether it is a square, that is, whether it can be written as q^2 for some positive integer q. What is the running time of your algorithm? write the pseudocode for the algorithm.

Solutions

Expert Solution


   pseudocode ://to find N is a square
isSquare(N):
   i=1
   while(i*i <N)://this loop breaks when i*i = N or i*i is greater than N
       i=i+1
   if(i*i ==N)://means N is a square
       return true
   else:
       return false
//complexity is :O(sqrt(N)) // O(N^(1/2))


Related Solutions

Given a positive integer k and an array A[1..n] that contains the quiz scores of n...
Given a positive integer k and an array A[1..n] that contains the quiz scores of n students in ascending order, design a divide and conquer algorithm to efficiently count the number of students that have quiz scores in (100(i − 1)/k, 100i/k] for integers 1 ≤ i ≤ k. Let group i be the set of students with quiz scores in (100(i − 1)/k, 100i/k] for integers 1 ≤ i ≤ k. The counting result should be stored in G[1..k],...
Consider an n×n square board, where n is a fixed even positive integer. The board is...
Consider an n×n square board, where n is a fixed even positive integer. The board is divided into n 2 unit squares. We say that two different squares on the board are adjacent if they have a common side. N unit squares on the board are marked in such a way that every unmarked square on the board is adjacent to at least one marked square. Determine the smallest possible value of N.
Determine the number of permutations of {1,2,3,...,n-1,n} where n is any positive integer and no even...
Determine the number of permutations of {1,2,3,...,n-1,n} where n is any positive integer and no even integer is in its natural position.
Let c be a positive number. A differential equation of the form below where k is...
Let c be a positive number. A differential equation of the form below where k is a positive constant, is called a doomsday equation because the exponent in the expression ky1+c is larger than the exponent 1 for natural growth. An especially prolific breed of rabbits has the growth term ky1.01. If 4 such rabbits breed initially and the warren has 28 rabbits after three months, then when is doomsday? (Doomsday is the finite time t=T such that . Round...
Statement: For a given integer N, print all the squares of positive integers where the square...
Statement: For a given integer N, print all the squares of positive integers where the square is less than or equal to N, in ascending order. Programming Tasks: Prompt the user to input the value of N Output to the screen all squares of positive integers <= N Tests: Item Test 1 Test 2 Test 3 Inputs: 50 9 100 Outputs: 1 4 9 16 25 36 49 1 4 9 1 4 9 16 25 36 49 64 81...
Let n be a positive integer. Prove that if n is composite, then n has a...
Let n be a positive integer. Prove that if n is composite, then n has a prime factor less than or equal to sqrt(n) . (Hint: first show that n has a factor less than or equal to sqrt(n) )
1. Consider production function of the form Q= f(H, K), where Q is the output measure...
1. Consider production function of the form Q= f(H, K), where Q is the output measure and H and K are hours worked and gross capital stock, respectively. Based on 33 observations we obtain the following results: ?og(?) = 0.129 + 0.448 ?og (?) + 0.559 ?og (?) (Standard Error) (0.546)      (0.704)           (0.816) R2= 0.886 a. Interpret the regression results. b. What is the output elasticity of hours worked? c. Verify that the coefficients of log(H) and log(K) are statistically...
4. Let n ≥ 8 be an even integer and let k be an integer with...
4. Let n ≥ 8 be an even integer and let k be an integer with 2 ≤ k ≤ n/2. Consider k-element subsets of the set S = {1, 2, . . . , n}. How many such subsets contain at least two even numbers?
that, given an integer N and an integer K, returns the minimum number of rounds that...
that, given an integer N and an integer K, returns the minimum number of rounds that are necessary for John to leave the casino with N chips, having played all-in no more than K times.
Show that there is only one positive integer k such that no graph contains exactly k...
Show that there is only one positive integer k such that no graph contains exactly k spanning trees.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT