Consider the following pseudocode for computing an array of prime numbers less t

Question

Consider the following pseudocode for computing an array of prime numbers less than or equal to n. INPUT n positive integer OUTPUT p E N*() is an array of primmbers less than or equal to Tu. ((n is the number of prime numbers less than or equal to n.) for k- 3,...Ti for j = 2, 3, k-1 then k is composite, stop loop and go to next k value end if statement end for loop If inner loop cycled all the way through then i = i + 1 then Pi = k end if statement end for loop The algorithm can be summarized in this way. We already know that 2 is prime, consider whether each integer from 3 to n is prime by dividing it by all integers greater than 2 that are less than it If one of those lesser numbers divides evenly into our candidate prime, then it's composite. Otherwise it is prime and we add that candidate number to the list This algorithm is implemented in the code prime list.slow.m. As the code name sug- gests, we can accelerate the speed of the code. That is the subject of this homework. Theorem 1 Ifm is not diisible by any prime number less than T, then is a prime number Theorem 2 Ifn is not divisible by any integer between two and Vn, then n is prime. 1. (10 points) Explain how the the two theorems above can be used to accelerate the code 2. (30 points) Write a pseudocode incorporating these changes with input n and output 3. (30 points) Create a Matlab function, titled primo.list that implements your pseu- primolist.slow.m created in class (and available via Blackboard) p E N), which is an array of all prime numbers less than or equal to n docode above. Your function should accept a positive integer ra as input and an array p E Nof prime number less than or equal to n as output.

Explanation / Answer

1)

a) acceleration due to theorem 1

proof for acceleration:

here the calculation is accelerated as we are not checking the divisibility by composite numbers

proof for correctness:

since any composite number is comprised of prime numbers only no need to check for divisibility of composite numbers

b)  acceleration due to theorem 2

proof for acceleration:

here the calculation is accelerated as we are not checking the divisibility by numbers greater than sqrt(n)

proof for correctness:

if a number n is divisible by b ( b > sqrt(n) ) then there exist another number a ( a < sqrt(b) ) such that a*b = n

hence as we already might have checked the divisibility with a, no need to check divisibility with b

2)

given psudo code:

p1=2
i=1
for k=3,....n
   for j=2,3...k-1
       if k=0 mod j
           then k is composite go to next k value
       end if statement
   end for loop
   if inner loop cycled all the way through
       then i=i+1
       pi = k
   end if statement
end for loop

modofied psudocode
p1 = 2
i=1
for k=3,...n
   j=1;
   while pj <= sqrt(k)
       if k = 0 mod pj
           then k is composite go to next k value
       end if statement
       j=j+1
   end while loop
   if while loop cycled all the way through
       then i=i+1
       pi=k
   end if statement
end foor loop

3)

prime_list.m

function p = prime_list(n)
p=[2];
for k = 3:n
j=1;
while p(j) <= sqrt(k)
if mod(k,p(j))==0
break
end
j=j+1;
end
if p(j)>sqrt(k)
p=[p k];
end
end

4)

p=[2,3....n]
i=1
for k=2...sqrt(n)
   for j=2....(n/k)
       remove j*k from p
   end
end

5)

function p = prime_seive(n)
p=2:n;
for k=2:sqrt(n)
for j=2:(n/k)
p=p(p~=(j*k));
end
end

Bonus:

function p1 = pi_array(p,n)
p1=[0];
j=1;
for i=2:n
if j<=length(p) && p(j)==i
p1(i)=p1(i-1)+1;
j=j+1;
else
p1(i)=p1(i-1);
end
end
  

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---