Supplementary Problem Link

http://qsmw.org.cn/oj/contest/1062

Supplementary Problem Process

1. Exercise 33.1: 3721 Numbers

Problem Analysis

The problem requires outputting all <span>3721</span> numbers within 200, sorted in ascending order.

This can be achieved using the <span>enumeration</span> knowledge learned in this lesson, by looping through all positive integers from <span>1~200</span> and checking if they meet the criteria.

The specific code is as follows:

AC Code

#include <bits/stdc++.h>
using namespace std;

int main()
{
    for(int i=1;i<=200;i++)
    {
        if(i%3==2 && i%7==1)
            cout << i << " ";
    }
    return 0;
}

2. Exercise 33.2: Prime Number Judgment

Problem Analysis

This is a classic <span>single-point prime number judgment</span> problem. Given an integer <span>N</span>, we need to determine whether <span>N</span> is a <span>prime number</span>.

First, let’s define what a <span>prime number</span> is. The problem also provides the definition:<span> it must be greater than 1, and this number has only 1 and N as its factors</span>.

Based on this definition, we first make a special case: if <span>N<2</span>, it is definitely not a prime number.

After excluding this special case, we can enumerate all numbers from <span>2 ~ N-1</span> to see if there is a <span>third factor</span> that can divide N. If found, it indicates that it is not a prime number.

For example:

Why is 7 a prime number: because we enumerated the numbers 2, 3, 4, 5, 6 and found that none can divide 7, indicating that 7 has only 1 and 7 as its factors, and since 7>1, it is a prime number.

Why is 16 not a prime number: because we enumerated the numbers 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 and found that 2, 4, 8 can divide 16, indicating that 16 has more than 2 factors, so it is not a prime number.<span>Of course, we only need to enumerate up to 2 because our goal is to find the third factor. Since 2 is already a third factor, there is no need to check the subsequent numbers.</span>

AC Code

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    if(n<2)
    {
        cout << "N";
        return 0;
    }
    for(int i=2;i<=n-1;i++) // The loop condition can be written as: for(int i=2; i*i<=n;i++), reason explained in the comment below
    {
        if(n%i==0)
        {
            cout << "N";
            return 0;
        }
    }
    cout << "Y"; // If none of the above returns, it means n is a prime number.
    return 0;
}

Students with extra capacity should note this characteristic: for an integer, we find that all its factors are symmetrically distributed around its <span>square root</span>, for example, 16 has factors 1, 2, 4, 8, 16, centered around the square root 4, with 2 factors on each side.

Therefore, when judging a single-point prime number, we only need to enumerate up to the square root of that number because: if we cannot find a third factor on the left side of the square root, we will not find it by enumerating all numbers.

This can greatly reduce the enumeration volume.

The loop condition can be written as: for(int i=2; i*i<=n;i++)

3. Exercise 33.3: Narcissistic Numbers

Problem Analysis

We can enumerate all three-digit numbers: 100-999, to see if they meet the characteristics of narcissistic numbers.

AC Code

#include <bits/stdc++.h>
using namespace std;

int main()
{
    for(int i=100;i<=999;i++)
    {
        // First, get all the digits of i
        int gw = i%10;
        int sw = i/10%10;
        int bw = i/100;
        // Judgment
        if(gw*gw*gw + sw*sw*sw + bw*bw*bw == i)
            cout << i << " ";     
    }
    return 0;
}

Instructor

The author of this article, Teacher Wu, is a CCF NOI certified instructor. If you wish to scientifically assess your child’s potential in learning C++, feel free to schedule a one-on-one learning ability assessment.