线性时间欧拉函数计算 [英] Linear time Euler's Totient Function calculation
问题描述
在冲浪一点后，我发现这个代码用于计算Euler phi值在线性时间使用Sieve of Eratostenes。但是不能理解这个代码中使用的主要逻辑，特别是在内部for循环和使用的想法
#define MAXN 3000000
int phi [MAXN + 1]，prime [MAXN / 10]，sz;
bitset< MAXN + 1>标记;
for（int i = 2; i <= MAXN; i ++）{
if（！mark [i]）{
phi [i] = i-1;
prime [sz ++] = i;
}
for（int j = 0; j
if（i％prime [j] == 0）{
phi [i * prime [j]] = phi [i] * prime [j];
break;
}
else phi [i * prime [j]] = phi [i] *（prime [j] -1）;
}
}
编码既不在这里也不在那里，但算法本身是辉煌。它与Eratosthenes筛没有什么关系。该方法有点让人联想到 Sieve of Sundaram ，因为它系统地生成多个素数，以便标记复合材料它比Sundaram的更好，每个复合材料完全交叉一次（无重写）。同样，每个phi值被计算并分配一次。
如果先改变一下，更容易理解代码：
枚举{N = 3000000};
矢量< unsigned>素数
矢量< unsigned> phi（N + 1）; //直接用数字索引，因此+1
向量< bool> is_composite（N + 1）; //直接用数字索引，因此+1
phi [1] = 1; // phi [0] is 0 already; phi [1]需要明确地设置
for（unsigned i = 2; i <= N; ++ i）
{
if（not is_composite [i] ）//它是一个素数
{
phi [i] = i - 1; // a prime is coprime to all numbers before it
primes.push_back（i）;
}
for（auto current_prime：primes）
{
unsigned ith_multiple = i * current_prime;
if（ith_multiple> N）
break;
is_composite [ith_multiple] = true;
if（i％current_prime）// i和current_prime are coprime - > phi是乘法在这种情况下
{
phi [ith_multiple] = phi [i] *（current_prime - 1）; //（current_prime - 1）== phi [current_prime]
}
else
{
phi [ith_multiple] = phi [i] * current_prime; //基于phi（p ^（k + 1））/ phi（p ^ k）== p
break;
}
}
}
phi（k）必须考虑三种不同情况：
（1）k是素数：phi（k）= k- （2）k = m * p其中m和p coprime和p prime：phi（k）= phi（m * p）= phi（m）* phi（p）= phi （m）*（p-1）
p（3）k = m * p，其中m = m'* p ^ n和m'和p coprime和p ：phi（k）= phi（m）* p
两个相关的数学事实列在关于 rel =nofollow>欧拉常数函数。情况1在外循环中处理，情况2是内循环中的条件的然后分支，情况3是 else 分支，也终止内部循环。情况2和3为更小数目的预先存在的phi值构建合成物的phi值，所有这些最终从派生物的phi值（在外循环中设置）中导出。
算法的亮度在于它安排要完成的工作的方式，使得每个值被精确计算一次并且在需要时已经被计算。它为复合体实现的递归是基于通过分解它的最小素因子有效地分割每个复合体：m = m'* p。这有利于根据上面的情况2和3的复合物的phi的计算，并且它导致产生没有重复的复合物的简单规则。其中，外部循环向内部循环呈现所有可能的m'（虽然对于i> N / 2，内部循环从不采用任何循环并且外部循环仅循环用于收集剩余的循环）。然后内部循环产生所有的复合物，它们是m'和不超过其自身素因子中最小的素因子的乘积。
代码已经验证从前100,000个phi值的列表。 org / A000010rel =nofollow> phi函数的OEIS页面。它被明确写成展示算法的工作;在被用于程序之前，它必须被检查，调整和硬化（特别是防止溢出）。
附录 - 如果任何人无意中跳过DanaJ的注释： is_composite [] array是多余的，因为给定的 i 的非复合性（原始性）可以通过测试 phi [i] 来确定零在外环。原因是复合材料的phi值向上传播 - 它们在早期迭代中计算，当 i 是其中的一个因素。另一种推理方法是当相应的phi值被计算时， is_composite [m] 只设置为 true 存储，并且那些值永远不能为零。因此，外层循环中的测试变成 if（phi [i] == 0）。和实施者（相对于纯粹的鉴赏家）可能更想看看DanaJ的评论...
After surfing a bit ,I found this code for calculating Euler's phi values in linear time using Sieve of Eratostenes .But failed to understand the main logic used in this code,specially what is done in the inner for loop and idea used in this loop for calculating phi value.It will be helpful if someone helps me understand this code.
#define MAXN 3000000
int phi[MAXN + 1], prime[MAXN/10], sz;
bitset <MAXN + 1> mark;
for (int i = 2; i <= MAXN; i++ ){
if(!mark[i]){
phi[i] = i-1;
prime[sz++]= i;
}
for (int j=0; j<sz && prime[j]*i <= MAXN; j++ ){
mark[prime[j]*i]=1;
if(i%prime[j]==0){
phi[i*prime[j]] = phi[i]*prime[j];
break;
}
else phi[i*prime[j]] = phi[i]*(prime[j]-1 );
}
}
The coding is neither here nor there but the algorithm as such is brilliant. It has little to do with the Sieve of Eratosthenes, though. The approach is somewhat reminiscent of the Sieve of Sundaram because it systematically produces multiples of primes in order to mark composites; it's better than Sundaram's in that each composite is crossed off exactly once (no overdraw). Likewise, each phi value is computed and assigned exactly once.
It is easier to understand the code if it is changed a little first:
enum { N = 3000000 };
vector<unsigned> primes;
vector<unsigned> phi(N + 1); // indexed directly with numbers, hence the +1
vector<bool> is_composite(N + 1); // indexed directly with numbers, hence the +1
phi[1] = 1; // phi[0] is 0 already; phi[1] needs to be set explicitly
for (unsigned i = 2; i <= N; ++i)
{
if (not is_composite[i]) // it's a prime
{
phi[i] = i - 1; // a prime is coprime to all numbers before it
primes.push_back(i);
}
for (auto current_prime: primes)
{
unsigned ith_multiple = i * current_prime;
if (ith_multiple > N)
break;
is_composite[ith_multiple] = true;
if (i % current_prime) // i and current_prime are coprime -> phi is multiplicative in this case
{
phi[ith_multiple] = phi[i] * (current_prime - 1); // (current_prime - 1) == phi[current_prime]
}
else
{
phi[ith_multiple] = phi[i] * current_prime; // based on phi(p^(k+1)) / phi(p^k) == p
break;
}
}
}
The computation of the values for phi(k) has to consider three different cases:
(1) k is prime: phi(k) = k - 1, which is trivial
(2) k = m * p with m and p coprime and p prime: phi(k) = phi(m * p) = phi(m) * phi(p) = phi(m) * (p - 1)
(3) k = m * p with m = m' * p^n and m' and p coprime and p prime: phi(k) = phi(m) * p
The two relevant mathematical facts are listed under Euler's product formula in the Wikipedia article on Euler's totient function. Case 1 is dealt with in the outer loop, case 2 is the then branch of the condition in the inner loop, and case 3 is the else branch which also terminates the inner loop. Cases 2 and 3 build phi values for composites out of preexisting phi values for smaller numbers, all of which ultimately derive from phi values for primes (set in the outer loop).
The brilliance of the algorithm lies in the way in which it arranges the work to be done, such that each value is computed exactly once and has already been computed when it is needed. The recursion it implements for composites is based on effectively splitting each composite by factoring out its smallest prime factor: m = m' * p. This facilitates the computation of the composite's phi as per cases 2 and 3 above, and it leads to a simple rule for producing composites without duplicates. Among other things, the outer loop presents all possible m' to the inner loop (although for i > N/2 the inner loop never takes any and the outer loop spins only for collecting the remaining primes). The inner loop then produces all composites that are the product of m' and a prime factor not exceeding the smallest of its own prime factors.
The code has been verified against a list of the first 100,000 phi values retrieved from the OEIS page for the phi function. It was written expressly to showcase the workings of the algorithm; before being used in a program it would have to be reviewed, tweaked, and hardened a bit (in particular to guard against overflow).
Addendum - In case anyone inadvertently skips DanaJ's comment: the is_composite[] array is superfluous because the non-compositeness (primality) of a given i can be ascertained by testing phi[i] for zero in the outer loop. The reason is that phi values for composites are propagated up - they get computed during an earlier iteration when i is one of their factors. Another way of reasoning is that is_composite[m] is only ever set to true when the corresponding phi value gets computed and stored, and those values can never be zero. Hence the test in the outer loop becomes if (phi[i] == 0). And implementers (as opposed to 'mere' connoisseurs) might want to look at DanaJ's comment even more closely...
这篇关于线性时间欧拉函数计算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
