The Gateway to Computer Science Excellence

0 votes

The following function computes an array $SPF$, where, for any integer $1 < i < 1000$, $SPF[i]$ is the smallest prime factor of $i$. For example, $SPF[6]$ is $2$, and $SPF[11]$ is $11$.

There are five missing parts in the following code, commented as $/* Blank */$. For each of them, copy the entire line with the comment and fill the blank appropriately in your answer sheet.

int SPF[1000]; void findSPF() { SPF[1] = 1; // Initializing SPF of every number to be itself for (int i = 2; i < 1000; i++) { _____; /* Blank 1 */ } // SPF of every even number is 2 for (int i = 4; i < 1000; i += 2) { SPF[i] = _____; /* Blank 2 */ } // For odd numbers, updating the SPFs of their multiples for (int i = _____; i * i < 1000; i++) { /* Blank 3 */ if (SPF[i] == i) { // No smaller factor of i found yet for (int j = _____; j < 1000; j+= i) { /* Blank 4 */ if (SPF[j] == j) { SPF[j] = _____; /* Blank 5 */ } } } } }

+1 vote

- int SPF[1000];
- void findSPF() {
- SPF[1] = 1;
- // Initializing SPF of every number to be itself
- for (int i = 2; i < 1000; i++) {
- SPF[i]=i; /* Blank 1 */
- }
- // SPF of every even number is 2
- for (int i = 4; i < 1000; i += 2) {
- SPF[i] = 2; /* Blank 2 */
- }
- // For odd numbers, updating the SPFs of their multiples
- for (int i = 3; i * i < 1000; i++) {
- /* Blank 3 */
- if (SPF[i] == i) {
- // No smaller factor of i found yet
- for (int j = i; j < 1000; j+= i) {
- /* Blank 4 */
- if (SPF[j] == j) {
- SPF[j] = SPF[i]; /* Blank 5 */
- }
- }
- }
- }
- }

52,218 questions

59,892 answers

201,086 comments

118,129 users