河北大学程序设计训练营

[TOC]

day17 求n以内最大的k个素数以及它们的和

本题要求计算并输出不超过n的最大的k个素数以及它们的和。

输入格式:

输入在一行中给出n(10≤n≤10000)和k(1≤k≤10)的值。

输出格式:

在一行中按下列格式输出:

1
素数1+素数2+…+素数k=总和值

其中素数按递减顺序输出。若n以内不够k个素数，则按实际个数输出。

列举两种方法：

1.适用于判断某个数n是否是素数

把[2,sqrt(n)]中的正数依次作为n的除数，如果存在能整除的，则n不为素数，否则就是素数

1
2
3
4
flag=1;
for(i=2;i<=sqrt(n);i++)
if(n%i==0)flag=0,break;
return flag;

返回值flag判断是否为素数。

2.适用于寻找较大区间内的所有素数

我们知道，素数就是除了1和本身没有因数的数，即素数不存在除了1和本身的因数。则任何一个数都是某个素数倍数（分解质因数）

则从2开始，把2作为第一个素数，将2的所有倍数都标记为非素数（合数），标记完后往上找没有被标记的数，是3，再把3的倍数标记，往上找，4=2*2，找到5，重复这个过程。
（code见完整代码）

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
#include<iostream>

using namespace std;

int main()
{
int a[10010]={0};
int n,k;
int i,j;
long sum=0;
    cin>>n>>k;
    i=2;
    while(i<n)
    {
        if(a[i]){i++;continue;}
        for(j=2*i;j<=n;j+=i)
            a[j]=1;
        i++;
    }//把区间内非素数的数标记

    i=0;
    while(i<k)
    {
        while(a[n])n--;
        if(i)cout<<"+";
        cout<<n;
        i++;
        sum+=n;
        n--;
        if(n==1)break;
    }

    cout<<"="<<sum;
}