+ 2

Can someone help me with solving this pseudocode?

Hi, I need your help with this task: Input: Array A with the length |A|=n of the natural numbers a in N ^ >=1 Output: Boolean value x:= 0; For i:= 1 to n do x:= x + A[i]; End for If x<2 then Return false; End if For i:= 2 to x -1 do If x mod i=0 then Return false; End if End for Return true; 1) Question: what is the output of the algorithm with input Array [2,3,5,7] ? 2) what does the algorithm in general? Does it reduce the input in the loop and calculates if the mod is 0? So it is basically looking if the two numbers (one of them is reduced)are multiples of each other? I feel very lost and would really appreciate your help!

28th Apr 2021, 5:42 PM
Belle
7 Respuestas
+ 2
This algorithm finds the sum of all the elements of the array, and then checks if the sum is a prime or not. And, if sum is less than 2, that means the array was [1,1], and 1 is not a candidate to test whether a number is prime or not. Consider this, array = [2 3 5 7] //x means sum x = 2+3+5+7 = 17 do: x%2 not = 0 x%3 not = 0 ... x%16 not = 0 // x is a prime // return True Ans: True
28th Apr 2021, 6:51 PM
Md. Faheem Hossain
Md. Faheem Hossain - avatar
+ 1
thank you so so much!! so for the array [2,3,5,7] the answer is true, because in the final loop the prime was = 0?
28th Apr 2021, 6:55 PM
Belle
+ 1
Let me optimize it a bit: x:= 0; For i:= 1 to n do x:= x + A[i]; End for If x<2 then Return false; End if If x mod 2=0 then Return False For i:= 3 to x //2 + 1, increment of 2 do If x mod i=0 then Return false; End if End for Return true;
28th Apr 2021, 6:55 PM
Md. Faheem Hossain
Md. Faheem Hossain - avatar
+ 1
What would the worst case complexity of this algorithm be ?
1st May 2021, 2:05 PM
Martin g
Martin g - avatar
0
👌
29th Apr 2021, 6:58 AM
Belle
0
thank you for your commitment
29th Apr 2021, 7:21 AM
Belle
0
Martin g O(n+k) where k is the sum of all the numbers of array A
1st May 2021, 5:31 PM
Md. Faheem Hossain
Md. Faheem Hossain - avatar