寒假训练——第四周（筛法）

A - 简单素数筛法

A - 简单素数筛法

思路：

• 筛素数
• 法一：埃氏筛（ $O(n\ast loglogn)$ )
• 法二：欧氏筛 也叫 线性筛 （ $O(n)$ )

埃氏筛代码如下：

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if(!st[i]) primes[cnt ++ ] = i;
        for (int j = i * i; j <= n; j += i)
            st[j] = true;
    }
}
1
2
3
4
5
6
7
8
9

线性筛代码如下：

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if(!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[i * primes[j]] = true;
            if(i % primes[j] == 0) break;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

---

B - Sum of Consecutive Prime Numbers

B - Sum of Consecutive Prime Numbers

思路：

• 连续素数和
• 线性筛 + 双指针（或暴力）

代码如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define mkpr make_pair
#define endl '\n'
#define x first
#define y second
#define int long long

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;

const int N = 10010, M = N * 2;
const int YB = 8, YM = 1e8;

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int T, cases;
int n, m, times;

int primes[N], cnt;
bool st[N];

void get_primes(int n)
{
    for (int i = 2; i <= N; i ++ )
    {
        if(!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[i * primes[j]] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

void solve()
{
    int res = 0;
    int sum = 0;
    for (int l = 0, r = 0; primes[r] <= n; r ++ )
    {
        sum += primes[r];
        while(sum > n)
        {
            sum -= primes[l];
            l ++;
        }
        if(sum == n) res ++;
    }
    cout << res << endl;

    return;
}

signed main()
{
    get_primes(N);
    
    T = 1;
    //fast;cin >> T;
    //scanf("%d", &T);

    //for (cases = 1; cases <= T; cases ++ )
    while(cin >> n, n)
        solve();

    return 0;
}
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
74
75
76
77
78
79
80
81
82
83
84
85
86

C - Semi-prime H-numbers

C - Semi-prime H-numbers

注意：

• 本题解的质数和素数同，，其实本来就相同，避免同学们弄混

思路：

• 线性筛（欧氏筛） 或 埃氏筛 的扩展（自然数 缩小到 h数）

具体实现：

• h数：所有模5余1的数
• 我们要找的H-semi-primes(H半质数)为 a * b其中a b为h素数
• 何为h素数：在h范围内，除了1和 该数本身外无法被其他h数整除的数（也可定义为只有1与该数本身两个正因数的h数），与自然素数定义很像
• 自然素数：指在大于1的自然数的范围内，除了1和该数自身外，无法被其他自然数整除的数（也可定义为只有1与该数本身两个正因数的自然数）
• 如此我们发现，我们要求的h素数只不过为范围为h数的素数，
• 如此一来我们仅需在h数的范围内做线性筛，即可求出所有的h数；同时，筛h素数时，若两个数都为h素数，则a * b为H-semi-primes(H半质数)

代码如下（和线性筛一模一样）：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define mkpr make_pair
#define endl '\n'
#define x first
#define y second
#define int long long

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;

const int N = 1e6 + 10, M = N * 2;
const int YB = 8, YM = 1e8;

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int T, cases;
int n, m, times;

int primes[N], cnt;
bool st[N];

bool Hprimes[N];
int ans[N];

void get_primes(int n)
{
    for (int i = 5; i <= n; i += 4 )
    {
        if(!st[i]) primes[cnt ++ ] = i;
        
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[i * primes[j]] = true;
            // st[primes[j]] = true 所以只判断st[i]是否为 h素数即可
            if(!st[i]) Hprimes[i * primes[j]] = true; 
            if(i % primes[j] == 0) break;
        }
    }
    
    for (int i = 1; i <= N; i ++ )
    {
        if(Hprimes[i]) ans[i] = ans[i - 1] + 1;
        else ans[i] = ans[i - 1];
    }
}

void solve()
{
    cout << n << " " << ans[n] << endl;
    
    return;
}

signed main()
{
    get_primes(N);
    
    T = 1;
    //fast;cin >> T;
    //scanf("%d", &T);

    //for (cases = 1; cases <= T; cases ++ )
    while(cin >> n, n)
        solve();

    return 0;
}
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
74
75
76
77
78
79
80
81
82
83
84
85
86