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
#include<iostream>
using namespace std;
const int MaxPrimeNum = 88499, MaxSize = 1000001, MaxSize1 = 31251;
int MinPrime[MaxSize], MaxPrime[MaxSize];       //分别记录可以整除MaxSize的最小与最大prime的index      //MaxPrime可以改成bit类型数组来记录是否是prime或者是否是Prime幂次方
int prime[MaxPrimeNum];
bool is_prime[MaxSize];
//自己修改，欧拉筛法求n以内的所有素数，存在prime数组里，index从1到num_prime-1 。
//并同时求出n以内的所有数的最小质因子与最大质因子，分别存在MaxPrime数组与MinPrime数组里
//复杂度O(n)
int i, j, len, num_prime = 1, tmpMaxIndex, tmp;
void euler_sieve(int n)
{
    i = 2;
    prime[len = tmpMaxIndex = MaxPrime[i] = MinPrime[i] = num_prime++] = i;
    is_prime[i] = true;
    for (i = 3; i < n; i += 2)
    {
        if (!MinPrime[i])
        {
            prime[len = tmpMaxIndex = MaxPrime[i] = MinPrime[i] = num_prime++] = i;
            is_prime[i] = true;
        }
        else
        {
            tmpMaxIndex = MaxPrime[i];
            len = MinPrime[i];
        }
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX