问题标签 [number-theory]

可能重复：
在 R 中生成一个素数列表，最多达到一定数量

在 R 语言中找到指定范围内的所有素数的优雅方法是什么？

给定除数的数量，我们必须找到第一个三角形数。

三角形数等于自然数之和。

我采用了从 2 开始取素数并排列它们的方法，以使生成的数字与三角形数匹配。

例如，假设我们有 5 个除数。我从 2 开始取素数(2,3,5)作为N=p1^a1*p2*a2*p3^a3. 除数的数量在(a1+1)(a2+1)....这里2,3,5可以取幂和排列。然后n^2+n=2k（k是从排列得到的值）。我检查 n 值是否为整数。

除此之外，我还没有找到任何有效的算法，有没有更优化的算法？

我正在尝试编写一个实现 Eratosthenes 筛子的素数生成器。但是，它在输出中包含一些合数（例如 25、49 和其他 5 和 7 的倍数）。

这是我的代码：

这是输出....

/blockquote>

1 2 3 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85 89 91 95 97

我的老师给了我们一道关于数学题的 acm 题。我试过了，但得到了 TLE。

这是问题所在。

Euler 的 Totient 函数 φ (n) [有时称为 phi 函数] 用于确定小于 n 且与​​ n 互质的数的数量。例如，1、2、4、5、7、8都小于9且与9互质，则φ(9)=6。HG 是 X Y 的大师。有一天 HG 想通过一个数学游戏教给 XY 一些关于 Euler 的 Totient 函数的知识。也就是说，HG 给出一个正整数 N，XY 告诉他的主人 2<=n<=N 的值，其中 φ(n) 是最大值。很快 HG 发现这对于 Lupus 入门的 XY 来说似乎有点容易，因为 XY 通过一个小程序很快就给出了正确的答案。所以HG做了一些改变。这次 XY 将告诉他 2<=n<=N 的值，其中 n/φ(n) 是最大值。这次XY遇到了一些困难，因为他没有足够的知识来解决这个问题。

输入有T个测试用例（1<=T<=50000）。对于每个测试用例，标准输入包含 2 ≤ n ≤ 10^100 的行。

输出 对于每个测试用例，应该有单行输出回答上面提出的问题。

样本输入 2 10 100

样本输出 6 30

这是我的代码。任何人都可以帮助改进它吗？

给定一个数 N，必须找到所有 i 的除数，其中 i>=1 和 i<=N。想不通。我必须使用素数分解吗？限制为 N<=10^9 样本输出：

如果我可以从函数中返回一个以上的值，我很感兴趣。例如考虑这样一个函数：扩展欧几里得算法。此输入描述的基本步骤是非负整数 a 和 b；输出是一个三元组 (d,i,j) 使得d=gcd(a,b)=i*a+j*b. 只是为了澄清我的问题的目标，我将编写一个简短的递归代码：

让 r 是这样的 a=r*b+q;

如何返回三胞胎？

Given a positive integer m, find four integers a, b, c, d such that a^2 + b^2 + c^2 + d^2 = m in O(m^2 log m). Extra space can be used.

I can think of an O(m^3) solution, but I am confused about the O(m^2 logm) solution..

给定两个整数，有没有一种简单的方法可以找到它们的最大同余模数？即a % n == b %n，或者甚至枚举所有这些？显然，我可以尝试比它们少的每个值，但似乎应该有更简单的方法。

我尝试用 gcds 做一些事情，但是你得到的只是 a % n == b % n == 0，这并不像我希望的那样酷，而且我很确定这不一定是最大的 n.

有任何想法吗？

以下代码向我显示了奇怪的错误

我不明白什么是手段，有人可以帮助我吗？

http://en.wikipedia.org/wiki/Binary_GCD_algorithm

这个 Wikipedia 条目有一个非常不令人满意的含义：二进制 GCD 算法曾经比标准 Euclid 算法效率高出 60%，但直到 1998 年，Knuth 得出结论，他的同时代算法的效率只有 15%。电脑。

又过了 15 年……今天这两种算法如何与硬件的进步相叠加？

二进制 GCD 是否继续在低级语言中优于欧几里得算法，但由于其在 Java 等高级语言中的复杂性而落后？还是现代计算中的差异没有实际意义？

我为什么在乎你可能会问？我今天碰巧不得不处理其中的 1000 亿个 :) 这是为生活在计算时代干杯（可怜的欧几里德）。