学霸秘籍信息学

FLS SDF2021 培训02期 第二课

上一节课是复习课, 今天信息课正式步入正轨。
主要内容：

  1. 老师讲了。。。。。
  2. 老师讲了。。。。
  3. 老师讲了。。。
  4. 老师讲了。。。

Problem-A 2-n之间的所有质数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
//题目描述
输入一个整数n（n<=10000)，输出n范围内所有的质数，每5个一行。

//输入
一个整数n(n<=10000)

//输出
输出2-n之间所有的质数，每行5个质数，每个数后面有一个空格。

//样例输入
15
//样例输出
2 3 5 7 11
13 
//提示
格式说明：一行如果满5个，则这一行结束后有回车，且这一行的最后一个数后面没有空格。

//提交
#include <iostream>
using namespace std;
int n,sam=0;
bool g(int n)   // 建议函数取名有意义, 如 bool isPrime(int n);
{
    for(int i=2;i*i<=n;i++)
    {
        if(n%i==0)
            return false;
    }
    return true;
}
int main()
{
    cin>>n;
    for(int i=2;i<=n;i++)   // 建议使用花括号, 使代码更清晰
        if(g(i))
        {
            cout<<i;
            sam++;
            if(sam==5)
                {
                    cout<<endl;
                    sam=0;  // 第一次提交忘记 sam 复位为0
                }
            else
                cout<<" ";
        }
    return 0;
}

Problem-B 哥德巴赫猜想

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//题目描述
著名的数学家哥德巴赫说：任意不小于6的偶数必定可分解成两个素数之和，例如10＝3+7。请编写
一个程序，对于输入的任意正偶数（不大于100000），将其分解成两个质数的和形式。如果有多种解，
输出第一个加数最小的那个解。

//输入
一个正偶数N（不大于100000）。

//输出
两个质数，它的和为N。

//样例输入
10
//样例输出
3 7
//提示

//提交
#include <iostream>
using namespace std;
int n;
bool g(int n)   // 建议函数取名有意义
{
    for(int i=2;i*i<=n;i++)
    {
        if(n%i==0)
            return false;
    }
    return true;
}
int main()
{
    cin>>n;
    for(int i=2;i<=n;i++)   // 可以优化为, 节省一半计算量: for(int i=3;i<=n;i=i+2)
        if(g(i)&&g(n-i))
        {
            cout<<i<<" "<<n-i<<endl;
            break;
        }
    return 0;
}

Problem-C 3n+1问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//题目描述
考虑如下序列生成算法：从整数n开始，如果n是偶数，把它除以2；如果n是奇数，把它乘3加1。用
新得到的值重复上述步骤，直到n=1时停止。例如，n=22时该算法生成的序列是：22，11，34，17，
52，26，13，40，20，10，5 ，16，8，4，2，1。
人们猜想对于任意整数n，该算法总能终止于n=1。这个猜想对于至少1000000内的整数都是正确的。
对于从给定的n，该序列的元素（包括1）个数被称为n的循环节长度。在上述例子中，22的循环节节
长度为16。输入两个数i和j，你的任务是计算i到j（包含i和j）之间的整数中，循环节长度的最大值。

//输入
输入只有一行，包含两个整数i和j。所有整数大于0，小于1000000。

//输出
输出只有一行，且仅有一个整数，为i到j之间整数中最大循环节长度。

//样例输入
1 10
//样例输出
20
//提示

//提交
#include <iostream>
using namespace std;
int i,j,sam,m=0;
void jg(int n)  // 建议函数取名有意义
{
    sam=1;
    while(n!=1)
    {
        if(n%2==0)
            n=n/2;
        else
            n=n*3+1;
        sam++;
    }
    if(sam>m)
        m=sam;
}
int main()
{
    cin>>i>>j;
    for(int k=i;k<=j;k++)
        jg(k);
    cout<<m<<endl;
    return 0;
}

Problem-D 亲密数对

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//题目描述
亲密数是一对的，如果整数A的全部真约数（包括1，不包括A本身）之和等于另一个数B；且整数B的
全部真约数（包括1，不包括B本身）之和等于A，则将整数A和B称为一对亲密数。 比如220和284，
220的真约数1、2、4、5、10、11、20、22、44、55、110之和等于284，284的真约数1、2、4、
71、142之和等于220。 
编写一个程序求N（1<＝N<=100000)以内的全部亲密数对。 

//输入
整数N。

//输出
输出N以内的全部亲密数对，每行一对，小的数在前，大的数在后，两数之间仅有一个空格。

//样例输入
3000
//样例输出
220 284
1184 1210
2620 2924
//提示

//提交
#include <iostream>
using namespace std;
int main()
{
    // TODO
    return 0;
}

Problem-E 孪生素数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
//题目描述
在质数的大家庭中，大小之差不超过2的两个质数称它俩为一对孪生素数，如2和3、3和5、17和19
等等。请你统计一下，在不大于自然数N的质数中，孪生素数的对数。

//输入
只有一行，一个自然数N。(N<=100 0000)。

//输出
只有一行，一个整数，表示N以内孪生素数的对数。

//样例输入
20
//样例输出
5
//提示

//提交
#include <iostream>
using namespace std;
int n,prime,tmp,sam=0;
bool p(int n)   // 判断的函数建议命名为: bool isXxx(xxx, xxx);
{
    for(int i=2;i*i<=n;i++)
    {
        if(n%i==0)
            return false;
    }
    return true;
}
int main()
{
    cin>>n;
    for(int i=2;i<=n-2;i++) // 可优化, p(）函数相对耗时, 尽可能有效调用, 节约时间
    {
        if(p(i))
        {
            prime=i;
            if(p(prime+1))
                sam++;
            if(p(prime+2))
                sam++;
        }
    }
    if(p(n-1)&&p(n))
        sam++;
    /*
    if(n==3)
        cout<<1<<endl;
    else if(n<=4)
    {
        cout<<0<<endl;
    }
    else
    {
        bool pre=false;
        for(int i=3;i<=n;i=i+2)
        {
            if(p(i))
            {
                if(pre)
                    sam++;
                else
                    pre=true;
            }
            else
                pre=false;
        }
        sam++;  // 2 and 3
    }
    */
    cout<<sam<<endl;
    return 0;
}

Problem-F 可逆素数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//题目描述
求a-b之间所有可逆素数。可逆素数是指：一个素数将其各位数字的顺序倒过来构成的反序数也是
素数。例如1009为素数，它的反序数9001也是素数，所以1009是可逆素数。这里我们规定可逆素数
比它的反序数小，即1009是可逆素数，而9001不算可逆素数。 

//输入
两个整数a,b。这里a,b<=10000，且a<=b.

//输出
输出a到b之间，所有可逆素数，每行一个。

//样例输入
10 20
//样例输出
13
17
//提示

//提交
#include <iostream>
using namespace std;
int main()
{
    // TODO
    return 0;
}

分享到