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))

venereology answered 1 year ago

Next > < Previous

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.

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 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...

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...

Question