+ 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!
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
+ 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?
+ 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;
+ 1
What would the worst case complexity of this algorithm be ?
0
👌
0
thank you for your commitment
0
Martin g O(n+k) where k is the sum of all the numbers of array A