IPA FE Subject B 2023 Question 1

Topic: Math & Numbers

A question IPA Japan published in 令和５年度 基本情報技術者試験 科目B 公開問題 問1, translated into English. ITPEC is based on the same exams.

From the answer group below, select the correct combination of answers to be inserted into A and B in the program. Here, the array index starts at 1.

The function findPrimeNumbers returns an array that stores all the prime numbers, and only the prime numbers, less than or equal to the integer given as the argument. Here, the integer given to the argument is 2 or greater.

[Program]
○ integer []: findPrimeNumbers(integer: maxNum)
integer []: pnList ← {} // array with 0 elements
integer: i, j
boolean: divideFlag
for (increase i from 2 to A by 1)
divideFlag ← true
/* The loop is not executed when the integer part of the positive square root of i is less than 2 */
for (increase j from 2 to the integer part of the positive square root of i by 1) // α
if (B)
divideFlag ← false
exit the for block marked α
endif
endfor
if (divideFlag is equal to true)
add the value of i to the end of pnList
endif
endfor
return pnList

Answer group

OptionAB

Explanation

A: maxNum, B: the remainder of i ÷ j is equal to 0 — the outer loop must test every candidate up to and including maxNum, and the inner loop must look for a divisor of i.

A number i of 2 or more is prime when no j from 2 up to the integer part of √i divides it: a divisor larger than √i always pairs with one smaller than it. So the test is "the remainder of i ÷ j is 0": it sets divideFlag to false and leaves the inner loop. For i = 2 and 3 the inner loop does not run, so both are kept. The loop over i must stop at maxNum, because the primes wanted are those less than or equal to it.

Run for maxNum from 2 to 200, only (a) returned exactly the primes every time; findPrimeNumbers(10) gives {2, 3, 5, 7}.

Answer (a)

Why not others:

  • •(b) — the quotient of i ÷ j is 1 only when j is more than half of i, which never happens for j ≤ √i once i ≥ 4, so every i from 4 up is rejected: findPrimeNumbers(10) returns {2, 3}
  • •(c) — runs i up to maxNum + 1, so a prime just above the limit slips in: findPrimeNumbers(10) returns {2, 3, 5, 7, 11}, and findPrimeNumbers(2) returns {2, 3}
  • •(d) — makes both mistakes: the quotient test rejects every i from 4 up, and the extra pass adds 3 when maxNum is 2

Key rule: To test whether n is prime, try divisors from 2 to ⌊√n⌋ and look for a remainder of 0; and a loop that should include its limit runs "to limit", not "to limit + 1".

Math & Numbers · AI-written, may contain errors

Practice this exam

This question comes from the past questions IPA Japan publishes, translated into English by ITPEC Practice. ITPEC Practice is an independent study tool and is not affiliated with IPA or ITPEC. See the original paper (PDF) or Report an issue.