algorithm - 在序列中,算法计算 coprimes

  显示原文与译文双语对照的内容
86 4

有一系列n <= 10 ^6整数,所有不超过m <= 3 *10^6,,我想计算它的中的多少互互对。如果两个数的最大公因式是 1,则两个数字是互素的。

在O ( n^2日志n ) 中可以以做得很简单,但这显然是慢的,因为限制会显示出更接近( n 日志n )的情况。它的中一件事就是解除所有数字,并且在每个数字中引发相同的素数。我还想计数有共同除数的对对。在群中,先计算所有的最小素数为 2,然后是 3,5和 等等,但我想,这是另一个死点。

时间:原作者:0个回答

120 3

我以前的答案是错误的,抱歉。我建议在这里修改:

一旦获得列表的每个数的数值,关联到列表中数字 l(p)的每个数字的数字。例如考虑素数 5,可以被 5除的列表数是 15,100和 255.然后( 5 ) =3 。

为了在O ( n 坐标) 中实现它,对列表中的每个数字进行迭代,循环遍历它的主要因素;。

然后,非互素的对数可以被p 整除

l(p)*(l(p) - 1)/2

将这个数字和所有的素数相比,你会得到列表中不是互互性( 请注意,l(p) 可以是 0 )的对数。假设这个和是D,那么答案是

M*(M-1)/2 - D

其中,M 是列表的长度。祝你好运

原作者:
...