罗小白


私信TA

用户名:Timmmmy

访问量:16270

签 名:

隔一年又回来刷题了...

等  级
排  名 139
经  验 7179
参赛次数 0
文章发表 46
年  龄 0
在职情况 学生
学  校
专  业

  自我简介:

有问题可以互相交流,共同提高 欢迎私信,请多指教:)

解题思路:
        从简单的来看,比如只有一位,那么必然只有 2,3,5,7

        再看两位,由题目要求,该两位数必为质数,且丢弃个位后,仍为质数。

        那么反过来看,从一位到两位,有什么规律呢?

        核心:以一位 5 为例,欲扩展到两位,最多只要判断 51,53,57,59 即可,也就是 (5*10) + 1 / +3 / +7 / +9

        【个位为0,2,4,6,8一定不为质数,5也排除在外

        再继续看,以53为例,欲扩展至三位,最多只要判断 531,533,537,539 即可  也就是 (53*10) + 1 / +3 / +7 / +9

        所以规律已经显而易见了

        (如果采用暴力算法,例如N=3,去遍历100~999再判断的话,必然超时,再怎么优化细节也不可行(主要是N=8太久了)


注意事项:
        判断质数函数 用的不是最优算法,有兴趣的同学再去研究一下吧


参考代码:

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

bool IsPrime(int num)
{
    if (num <= 3)  return num > 1;
    int s = sqrt(num);
    for (int i = 2; i <= s; ++i) {
        if (num % i == 0)   return false;
    }
    return true;
}

int main()
{
    int n;
    while (cin >> n) {
        // int型链表
        list<int> li;
        // 迭代器
        list<int>::iterator iter;
        int i, j, tmp;
        // 记录当前n所对应的特殊质数的个数,比如n=1时,count=4
        int count = 0;
        // 初始化为 2 3 5 7
        li.push_back(2);
        li.push_back(3);
        li.push_back(5);
        li.push_back(7);
        // 从n=1开始,扩展到题目要求的n
        for (i = 1; i < n; ++i) {
            // 更新count
            count = li.size();
            // 从list第一个数开始处理
            iter = li.begin();
            // 一共处理count个数
            while (count != 0) {
                // 优化效率,防止多次运算
                tmp = (*iter) * 10;
                // 取完数后,指针指向下一个待处理的数
                iter++;
                // 删除已记录在tmp的那个数
                li.pop_front();    
                // 更新count    
                count--;
                // 对应的 +1 +3 +7 +9,想写循环的话:tmp += 2,但是这样写更直观
                if (IsPrime(tmp + 1)) {
                    li.push_back(tmp + 1);
                }
                if (IsPrime(tmp + 3)) {
                    li.push_back(tmp + 3);
                }
                if (IsPrime(tmp + 7)) {
                    li.push_back(tmp + 7);
                }
                if (IsPrime(tmp + 9)) {
                    li.push_back(tmp + 9);
                }
                
            }
        }
        // 输出即可
        for (iter = li.begin(); iter != li.end(); ++iter) {
            cout << (*iter) << endl;
        }    
    }
    return 0;
}


解题思路:
        嫌上面麻烦的同学,这里有一份更直接的AC代码
注意事项:
        定向输出!
参考代码:

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

void outputArr(int A[], int size)
{
    for (int i = 0; i < size; ++i) {
        cout << A[i] << endl;
    }
}

int main()
{
    int n;
    while (cin >> n) {
        
        int N1[] = { 2,3,5,7 };
        int N2[] = { 23,29,31,37,53,59,71,73,79 };
        int N3[] = { 233,239,293,311,313,317,373,379,593,599,719,733,739,797 };
        int N4[] = { 2333,2339,2393,2399,2939,3119,3137,3733,3739,3793,3797,5939,7193,7331,7333,7393 };
        int N5[] = { 23333,23339,23399,23993,29399,31193,31379,37337,37339,37397,59393,59399,71933,73331,73939 };
        int N6[] = { 233993,239933,293999,373379,373393,593933,593993,719333,739391,739393,739397,739399 };
        int N7[] = { 2339933,2399333,2939999,3733799,5939333,7393913,7393931,7393933 };
        int N8[] = { 23399339,29399999,37337999,59393339,73939133 };

        switch (n)
        {
        case 1: outputArr(N1, 4); break;
        case 2: outputArr(N2, 9); break;
        case 3: outputArr(N3, 14); break;
        case 4: outputArr(N4, 16); break;
        case 5: outputArr(N5, 15); break;
        case 6: outputArr(N6, 12); break;
        case 7: outputArr(N7, 8); break;
        case 8: outputArr(N8, 5); break;
        default:
            break;
        }
    }
    return 0;
}


 

0.0分

9 人评分

  评论区