第2328试题

题目描述

判断一个正整数 n 是否能被一个“幸运数”整除。幸运数是指一个只包含 4 或 7 的正整数，如 7 、47 、477 等都是“幸运数”，17 、42 则不是“幸运数”。

输入要求

一行一个正整数 n ，\(1 \leq n\leq 1000\)。

输出要求

一行一个字符串，如果能被幸运数整除输出“YES”，否则输出“NO”。

个人思路

  其实一开始看到这个题目，我的想法是做一个“幸运数”的生成器，然后筛选出指定范围内的“幸运数”，用来除正整数 n 。这样在枚举运算时尝试次数会更少，但是实现起来比起下面的方法会更加麻烦。
  这里采用了一个更加暴力的方法：把小于 n 的数全部除一遍，然后从中筛选可整除的“幸运数”。（如果想要优化一下的话可以考虑只枚举到\(\sqrt n\)）那么我们现在就有了两个需要检查的条件：
  1.是"幸运数"：“幸运数”是只包含 4 或 7 的正整数，那就需要对除数逐位检查是否为 4 或 7，这里需要用到一个以后常用的小技巧：交替模（%）10 和除（/）10 以分离数的每一位。每次分离出除数的一位判断是否是 4 或 7 ，如果是则检查下一位，只要不是就立即跳出循环，检查下一个数。
  2.可被整除：对筛选出的“幸运数”加以标记后（flag = 1）除正整数 n ，判断是否整除。如找到可整除的“幸运数”则输出“YES”，如没有任何（可整除的）“幸运数”则最终输出“NO”。

参考代码

#include <iostream>

using namespace std;

int main()
{
  int n = 0, i = 0, j = 0, flag = 0;
    cin >> n;
    for (i = 1; i <= n; i++) //用比n小的所有数除数n，寻找其中可整除的“幸运数”
    {
        j = i;
        do//循环检查除数的每一位是否只有4或者7，筛选“幸运数”
        {
            if (j % 10 == 4 || j % 10 == 7)
                flag = 1;
            else//若出现非4或7的数则说明不是“幸运数”，终止循环
            {
                flag = 0;
                break;
            }
            j /= 10;//检查除数的下一位
        } while (j);//除数的每一位都检查过，终止循环

        if (flag == 1 && n % i == 0)// 找到可整除的“幸运数”
            cout << "YES" << endl;
    }
    if (flag == 0)//没有找到任何可整除的“幸运数”
        cout << "NO" << endl;
    return 0;
}