2013-team5/prime

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
/*
    素数和欧拉函数
    O(n)
    cnt < 4000
    By Kotomi
*/


const int maxPrime = 1000001;
int Eul[maxPrime];
int prime[maxPrime];

int Prime(int n = maxPrime)
{
    memset(Eul, 0, sizeof(Eul));
    Eul[1] = 1;
    int cnt = 0;
    for (int i = 2; i < n; i++){
    if (!Eul[i]){
            prime[cnt++] = i;
            Eul[i] = i - 1;
        }    
    for (int j = 0; j <= cnt; j++){
        if (i * prime[j] >= n) break;
        Eul[i * prime[j]] = 1;
        if (i % prime[j] == 0){
                    Eul[i * prime[j]] = Eul[i] * prime[j];
                    break;
                }
            else
                Eul[i * prime[j]] = Eul[i] * (prime[j] - 1);
    }
    }
    return cnt;
}

}}}

/*
    素数和欧拉函数
    O(n)
    cnt < 4000
    By Kotomi
*/
const int maxPrime = 1000001;
int Eul[maxPrime];
int prime[maxPrime];
int Prime(int n = maxPrime)
{
    memset(Eul, 0, sizeof(Eul));
    Eul[1] = 1;
    int cnt = 0;
    for (int i = 2; i < n; i++){
    if (!Eul[i]){
            prime[cnt++] = i;
            Eul[i] = i - 1;
        }    
    for (int j = 0; j <= cnt; j++){
        if (i * prime[j] >= n) break;
        Eul[i * prime[j]] = 1;
        if (i % prime[j] == 0){
                    Eul[i * prime[j]] = Eul[i] * prime[j];
                    break;
                }
            else
                Eul[i * prime[j]] = Eul[i] * (prime[j] - 1);
    }
    }
    return cnt;
}